Изменения

Пусть длина наибольшей общей подстроки будет <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, является длиной наибольшей общей подстроки. Таким образом, требуется с помощью бинарного поиска найти это значение. В ходе работы придется проверять наличие общей подстроки заданной длины. Для этого будем использовать хеширование, чтобы улучшить асимптотику алгоритма. Делается это Алгоритм является эвристическим и может выдавать неверный ответ, так как совпадение хешей строк не гарантирует их равенство. Алгоритм работает следующим образом:<br> 1) У строки <tex>s</tex> хешируем подстроки заданной длины и полученные хеши записываем в Set.<br>2) У строки <tex>t</tex> хешируем подстроки заданной длины и в случае совпадения хеша с элементом Set выполняем посимвольную проверку на совпадение подстрок, чтобы избежать неверного ответа.<br>