Изменения

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