Изменения

{{Задача|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; [1 .. 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 [1 .. 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>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>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. [[Категория:Алгоритмы и структуры данных]][[Категория:Поиск подстроки в строке]][[Категория:Точный поиск]][[Категория:Хеширование]]