Изменения

Имеются строки <tex>S</tex> и <tex>T</tex> такие, что элементы этих строк <tex>-</tex> символы из конечного алфавита <tex> \sum </tex>. Говорят, что строка <tex>Z</tex>[1 .. m] </tex> является подстрокой строки <tex>S</tex>[1 .. n]</tex>, если существует такой индекс <tex>k</tex> &isin; \in [0 .. n - m]</tex>, что для любого <tex>i</tex> &isin; \in [1 .. m] </tex> справедливо <tex>S[k + i] = Z[i]</tex>. Требуется найти такую строку <tex>Z</tex>, максимальной длины, что <tex>Z</tex> является и подстрокой <tex>S</tex>, и подстрокой <tex>T</tex>.

Данный алгоритм основывается на методе половинного деления. Пусть длина наибольшей общей подстроки будет <tex>x</tex>. Заметим, что у строк <tex>S</tex> и <tex>T</tex> обязательно найдется общая подстрока длины <tex>y</tex> &isin; \in [0 .. <tex>x]</tex>], так как в качестве такой строки можно взять префикс наибольшей общей подстроки. Рассмотрим функцию <tex>f</tex> : [0 .. \min(len(<tex>S</tex>), len(<tex>T</tex>))] &rarr; \rightarrow \{0, 1\}</tex>, которая для <tex>i</tex> из области определения равна 1, если у строк <tex>S</tex> и <tex>T</tex> есть общая подстрока длины <tex>i</tex>, иначе она равна 0. Согласно замечанию, функция <tex>f</tex> должна по мере возрастания <tex>i</tex> быть равной 1 до некоторого момента, а затем обращаться в 0. Собственно, максимальное значение, при котором функция принимает значение 1, является длиной наибольшей общей подстроки. Таким образом требуется с помощью бинарного поиска найти это значение. В ходе работы придется проверять наличие общей подстроки заданной длины. При этом предполагается использовать хеширование, чтобы улучшить асимптотику алгоритма. Делается это следующим образом: <br>1) у строки <tex>S</tex> хешируем подстроки заданной длины и полученные хеши записываем в Set. <br>2) у строки <tex>T</tex> хешируем подстроки заданной длины и в случае совпадения хеша с элементом Set выполняем посимвольную проверку на совпадение подстрок. <br>Предполагается, что хеширование будет проводится так же, как и в [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа|алгоритме Рабина-Карпа]].

Проведем оценку асимптотики времени работы предложенного алгоритма. Посмотрим сколько нам потребуется действий на каждом шаге бинарного поиска. Во-первых, хеширование подстрок строки <tex>S</tex> и запись их в Set требует <tex>O(len(<tex>S))</tex>)) шагов. Во-вторых, хеширование подстрок строки <tex>T</tex> и проверка их наличия в Set требует <tex>O(len(<tex>T))</tex>)). В приведенных рассуждениях предполагается, что операции записи в Set и проверка наличия элемента в Set работают за амортизированную <tex>O(1)</tex>. Поскольку хешировали с помощью [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа|этого]] метода, то это занимает линейное время. Значит,на каждый шаг бинарного поиска требуется <tex>O(max(len(<tex>S</tex>), len(<tex>T)))</tex>))) действий. На самом деле требуется несколько больше времени, поскольку совпадение хешей не дает гарантии совпадения подстрок, однако чтобы это было справедливо с большой вероятностью, достаточно проверить совпадение лишь нескольких произвольных символов, вместо полной проверки. Тогда на это потребуется некоторое константное число операций, что маскируется с помощью <tex>O</tex>. Заметим, что всего для завершения бинарного поиска потребуется <tex>O(\log(\min(len(<tex>S</tex>), len(<tex>T))))</tex>)))) шагов. Следовательно, суммарное время работы алгоритма будет <tex>O(\log(\min(len(<tex>S</tex>), len(<tex>T</tex>))) * \max(len(<tex>S</tex>), len(<tex>T)))</tex>))) действий.