Изменения

{{Задача|definition ==Постановка задачи==Имеются строки <tex>Ss</tex> и <tex>Tt</tex> такие, что элементы этих строк <tex>-</tex> символы из конечного алфавита <tex> \sum Sigma </tex>. ГоворятТребуется найти такую строку <tex>z</tex> максимальной длины, что строка <tex>Zz</tex>[1 .. m] является и подстрокой строки <tex>Ss</tex>[1 .. n], если существует такой индекс и подстрокой <tex>kt</tex> &isin; [0 .. n - m]}}{{Определение|definition = Будем говорить, что для любого строка <tex>iz[0 \, \ldots \, m-1]</tex> &isin; [1 .. m] справедливо является подстрокой строки <tex>Ss[k + i] = Z[i0 \, \ldots \, n-1]</tex>. Требуется найти такую строку , если существует такой индекс <tex>Zk \in [0\, \ldots \, n - m]</tex>, максимальной длины, что для любого <tex>Zi \in [0 \, \ldots \, m-1]</tex> является и подстрокой справедливо <tex>S</tex>, и подстрокой <tex>Ts[k + i] = z[i]</tex>.}}

==Алгоритм==Данный алгоритм основывается на методе половинного деления. Пусть длина наибольшей общей подстроки будет <tex>x</tex>. Заметим, что у строк <tex>Ss</tex> и <tex>Tt</tex> обязательно найдется общая подстрока длины <tex>y</tex> &isin; \in [0 .. <tex>\ldots x]</tex>], так как в качестве такой строки можно взять префикс наибольшей общей подстроки. Рассмотрим функцию предикат <tex>f</tex> : \colon [0 .. \ldots \min(len(<tex>S</tex>)|s|, len(<tex>T</tex>)|t|)] &rarr; \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предикат истинен, является длиной наибольшей общей подстроки. Таким образом , требуется с помощью бинарного [[Целочисленный двоичный поиск|двоичного поиска ]] найти это значение. В ходе работы придется проверять наличие общей подстроки заданной длины. При этом предполагается Для этого будем использовать хеширование, чтобы улучшить асимптотику алгоритма. Делается это Алгоритм является эвристическим и может выдавать неверный ответ, так как совпадение хешей строк не гарантирует равенство строк. Поэтому нужно выполнить проверку нескольких случайных символов подстрок на совпадение, проиграв при этом по времени работы. Алгоритм работает следующим образом: 1)  * у строки <tex>Ss</tex> хешируем подстроки заданной длины и полученные хеши записываем в Set. 2) , * у строки <tex>Tt</tex> хешируем подстроки заданной длины и в случае совпадения хеша с элементом Set выполняем посимвольную проверку проверяем несколько случайных символов подстрок на совпадение подстрок. Предполагается, что хеширование будет проводится  Хеширование будем производить так же, как и в [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа|алгоритме Рабина-Карпа]].

Тогда <tex>i</tex> — длина подстроки, найденная с помощью [[Целочисленный двоичный поиск|двоичного поиска]]. <tex>f(i)</tex> — предикат, описанный в алгоритме.  '''bool''' f(i: '''int'''): hashes = хеши подстрок строки <tex>s</tex> длины <tex>i</tex> '''for''' j = 0 '''to''' |t| − i hash = hash(t[j ... j + i − 1]) '''if''' hash '''in''' hashes '''if''' совпали несколько случайных символов подстрок '''return''' ''true'' '''else''' '''continue''' '''return''' ''false'' == Время работы ==Проведем оценку асимптотики времени работы предложенного алгоритма. Посмотрим, сколько нам потребуется действий на каждом шаге двоичного поиска. Во-первых, хеширование подстрок строки <tex>s</tex> и запись их в Set требует <tex>O(|s|)</tex> шагов. Во-вторых, хеширование подстрок строки <tex>t</tex> и проверка их наличия в Set требует <tex>O(|t|)</tex>. Проверка на совпадение нескольких символов подстрок требует константное время. Значит, на каждый шаг двоичного поиска требуется <tex>O(\max(|s|, |t|))</tex> действий. Заметим, что всего для завершения двоичного поиска длины потребуется <tex>O(\log(\min(|s|, |t|)))</tex> шагов. Следовательно, суммарное время работы алгоритма будет <tex>O(\log(\min(|s|, |t|)) \cdot \max(|s|, |t|))</tex> действий. == См. также ==* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]* [[Задача о наибольшей общей подстроки требуется вызвать findGCS со следующими параметрами:подпоследовательности]]  result = findGCS= Источники информации ==* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 3-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2014. — 1328 с.: ил. — ISBN 978-5-8459-1794-2 (0, nрус.)— страницы 1036–1041.

==Время работы==[[Категория:Алгоритмы и структуры данных]]Проведем оценку асимптотики времени работы предложенного алгоритма. Посмотрим сколько нам потребуется действий на каждом шаге бинарного поиска. Во-первых, хеширование подстрок строки <tex>S</tex> и запись их в Set требует O(len(<tex>S</tex>)) шагов. Во-вторых, хеширование подстрок строки <tex>T</tex> и проверка их наличия в Set требует O(len(<tex>T</tex>)). В приведенных рассуждениях предполагается, что операции записи в Set и проверка наличия элемента в Set работают за амортизированную O(1). Поскольку хешировали с помощью [[Категория:Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа|этого]] метода, то это занимает линейное время. Значит,на каждый шаг бинарного поиска требуется O(max(len(<tex>S</tex>), len(<tex>T</tex>))) действий. На самом деле требуется несколько больше времени, поскольку совпадение хешей не дает гарантии совпадения подстрок, однако чтобы это было справедливо с большой вероятностью, достаточно проверить совпадение лишь нескольких произвольных символов, вместо полной проверки. Тогда на это потребуется некоторое константное число операций, что маскируется с помощью O. Заметим, что всего для завершения бинарного поиска потребуется O(log(min(len(<tex>S</tex>), len(<tex>T</tex>)))) шагов. Следовательно, суммарное время работы алгоритма будет O(log(min(len(<tex>S</tex>), len(<tex>T</tex>))) * max(len(<tex>S</tex>), len(<tex>T</tex>))) действий.== Литература ==[[Категория:Точный поиск]]Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы[[Категория: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.Хеширование]]