Изменения

Пусть длина наибольшей общей подстроки будет <tex>x</tex>. Заметим, что у строк <tex>s</tex> и <tex>t</tex> обязательно найдется общая подстрока длины <tex>y \in [0 .. x]</tex>, так как в качестве такой строки можно взять префикс наибольшей общей подстроки. Рассмотрим функцию <tex>f : [0 .. \min(|s|, |t|)] \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, является длиной наибольшей общей подстроки. Таким образом, требуется с помощью бинарного поиска найти это значение. В ходе работы придется проверять наличие общей подстроки заданной длины. Для этого будем использовать хеширование, чтобы улучшить асимптотику алгоритма. Алгоритм является эвристическим и может выдавать неверный ответ, так как совпадение хешей строк не гарантирует их равенство. Однако неверного ответа можно избежать, выполнив посимвольную Поэтому нужно выполнить проверку нескольких символов подстрок на совпадение, но проиграв при этом по времени работы. Алгоритм работает следующим образом:

2) У строки <tex>t</tex> хешируем подстроки заданной длины и в случае совпадения хеша с элементом Set выполняем посимвольную проверку проверяем несколько символов подстрок на совпадение подстрок.