Изменения

Перейти к: навигация, поиск
Стилистические правки
}}
{{Определение
|definition = ГоворятБудем говорить, что строка <tex>z[1 .. \mathinner{\ldotp\ldotp} m]</tex> является подстрокой строки <tex>s[1 .. \mathinner{\ldotp\ldotp} n]</tex>, если существует такой индекс <tex>k \in [0 .. \, \mathinner{\ldotp\ldotp}\, n - m]</tex>, что для любого <tex>i \in [1 .. \mathinner{\ldotp\ldotp} m]</tex> справедливо <tex>s[k + i] = z[i]</tex>.
}}
== Алгоритм ==
Пусть длина наибольшей общей подстроки будет <tex>x</tex>. Заметим, что у строк <tex>s</tex> и <tex>t</tex> обязательно найдется общая подстрока длины <tex>y \in [0 .. \mathinner{\ldotp\ldotp} x]</tex>, так как в качестве такой строки можно взять префикс наибольшей общей подстроки. Рассмотрим предикат <tex>f \colon [0 .. \mathinner{\ldotp\ldotp} \min(|s|, |t|)] \rightarrow \{0, 1\}</tex>, который для <tex>i</tex> из области определения истинен, если у строк <tex>s</tex> и <tex>t</tex> есть общая подстрока длины <tex>i</tex>, иначе ложен. Согласно замечанию, предикат <tex>f</tex> должен по мере возрастания <tex>i</tex> быть истинным до некоторого момента, а затем обращаться в ложь. Собственно, максимальное значение, при котором предикат истинен, является длиной наибольшей общей подстроки. Таким образом, требуется с помощью [[Целочисленный двоичный поиск|двоичного поиска]] найти это значение. В ходе работы придется проверять наличие общей подстроки заданной длины. Для этого будем использовать хеширование, чтобы улучшить асимптотику алгоритма. Алгоритм является эвристическим и может выдавать неверный ответ, так как совпадение хешей строк не гарантирует равенство строк. Поэтому нужно выполнить проверку нескольких случайных символов подстрок на совпадение, проиграв при этом по времени работы. Алгоритм работает следующим образом:
1) У строки <tex>s</tex> хешируем подстроки заданной длины и полученные хеши записываем в Set.
<tex>f(i)</tex> — предикат, описанный в алгоритме.
'''bool''' f(i: '''int''')
hashes = хеши подстрок строки <tex>s</tex> длины <tex>i</tex>
'''for''' j = 1 '''to''' |t| − i + 1
130
правок

Навигация