Изменения

{{Задача|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; <tex>\mathbbrightarrow \{Z0, 1\}</tex>, которая который для <tex>i</tex> из области определения равна <tex>i</tex>истинен, если у строк <tex>Ss</tex> и <tex>Tt</tex> есть общая подстрока длины <tex>i</tex>, иначе она равна 0ложен. Согласно замечанию, функция предикат <tex>f</tex> должна должен по мере возрастания <tex>i</tex> строго монотонно возрастать быть истинным до некоторого момента, а затем обращаться в 0. Таким образом на области определения у функции <tex>f</tex> достигается максимумложь. Собственно, этот максимум и максимальное значение, при котором предикат истинен, является длиной наибольшей общей подстроки у строк <tex>S</tex> и <tex>T</tex>, так как функция <tex>f</tex> специально так определена. Таким образом , требуется с помощью бинарного [[Целочисленный двоичный поиск|двоичного поиска ]] найти максимум функции <tex>f</tex> на ее множестве определенияэто значение. В ходе работы придется проверять наличие общей подстроки заданной длины. При этом предполагается Для этого будем использовать хэшированиехеширование, чтобы улучшить асимптотику алгоритма. Делается это следующим образом: 1) у строки <tex>S</tex> хэшируем подстроки заданной длины Алгоритм является эвристическим и полученные хэши записываем в Setможет выдавать неверный ответ, так как совпадение хешей строк не гарантирует равенство строк. 2) у строки <tex>T</tex> хэшируем подстроки заданной длины и в случае совпадения хэша с элементом Set выполняем посимвольную Поэтому нужно выполнить проверку нескольких случайных символов подстрок на совпадение подстрок. Предполагается, что хэширование будет проводится так же, как и в [[Поиск подстроки в строке с использованием хешированияпроиграв при этом по времени работы. Алгоритм Рабина-Карпа|алгоритме Рабина-Карпа]].работает следующим образом:

* у строки <tex>s</tex> хешируем подстроки заданной длины и полученные хеши записываем в Set, * у строки <tex>t</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>Ss</tex> и запись их в Set требует O(len(<tex>SO(|s|)</tex>)) шагов. Во-вторых, хэширование хеширование подстрок строки <tex>Tt</tex> и проверка их наличия в Set требует O(len(<tex>TO(|t|)</tex>)). В приведенных рассуждениях предполагается, что операции записи в Set и проверка наличия элемента в Set работают за амортизированную O(1). Поскольку хэшировали с помощью [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа|этого]] метода, то это занимает линейное Проверка на совпадение нескольких символов подстрок требует константное время. Значит,на каждый шаг бинарного двоичного поиска требуется <tex>O(\max(len(<tex>S</tex>|s|, |t|)), len(<tex>T</tex>))) действий. На самом деле требуется несколько больше времени, поскольку совпадение хэшей не дает гарантии совпадения подстрок, однако чтобы это было справедливо с большой вероятностью, достаточно проверить совпадение лишь нескольких произвольных символов, вместо полной проверки. Тогда на это потребуется некоторое константное число операций, что маскируется с помощью O. Заметим, что всего для завершения бинарного двоичного поиска потребуется <tex>O(\log(\min(len(<tex>S</tex>|s|, |t|))), len(<tex>T</tex>)))) шагов. Следовательно, суммарное время работы алгоритма будет <tex>O(\log(\min(len(<tex>S</tex>)|s|, len(<tex>T</tex>|t|))) * \cdot \max(len(<tex>S|s|, |t|))</tex>)действий. == См. также ==* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]* [[Задача о наибольшей общей подпоследовательности]] == Источники информации ==* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 3-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", len2014. — 1328 с.: ил. — ISBN 978-5-8459-1794-2 (<tex>T</tex>)рус.)) действий— страницы 1036–1041. [[Категория:Алгоритмы и структуры данных]][[Категория:Поиск подстроки в строке]][[Категория:Точный поиск]][[Категория:Хеширование]]