Изменения
→Алгоритм
Имеются строки <tex>S</tex> и <tex>T</tex> такие, что элементы этих строк <tex>-</tex> символы из конечного алфавита <tex> \sum </tex>. Говорят, что строка <tex>Z</tex>[1 .. m] является подстрокой строки <tex>S</tex>[1 .. n], если существует такой индекс <tex>k</tex> ∈ [1 .. n - m], что для любого <tex>i</tex> ∈ [1 .. m] справедливо <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> ∈ [0 .. <tex>x</tex>], так как в качестве такой строки можно взять префикс наибольшей общей подстроки. Рассмотрим функцию <tex>f</tex> : [1 .. min(len(<tex>S</tex>), len(<tex>T</tex>))] → <tex>\mathbb{Z}</tex>, которая для <tex>i</tex> из области определения равна <tex>i</tex>, если у строк <tex>S</tex> и <tex>T</tex> есть общая подстрока длины <tex>i</tex>, иначе она равна 0. Согласно замечанию, функция <tex>f</tex> должна по мере возрастания <tex>i</tex> строго монотонно возрастать до некоторого момента, а затем обращаться в 0. Таким образом на области определения у функции <tex>f</tex> достигается максимум. Собственно, этот максимум и является длиной наибольшей общей подстроки у строк <tex>S</tex> и <tex>T</tex>, так как функция <tex>f</tex> специально так определена. Таким образом требуется с помощью бинарного поиска найти максимум функции <tex>f</tex> на ее множестве определения. В ходе работы придется проверять наличие общей подстроки заданной длины. При этом предполагается использовать хэширование, чтобы улучшить асимптотику алгоритма. Делается это следующим образом: 1) у строки <tex>S</tex> хэшируем подстроки заданной длины и полученные хэши записываем в Set. 2) у строки <tex>T</tex> хэшируем подстроки заданной длины и в случае совпадения хэша с элементом Set выполняем посимвольную проверку на совпадение подстрок. Предполагается, что хэширование будет проводится так же, как и в [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа|алгоритме Рабина-Карпа]].
