Изменения

{{Задача|definition ==Постановка задачи==Имеются строки <tex>s</tex> и <tex>t</tex> такие, что элементы этих строк <tex>-</tex> символы из конечного алфавита <tex> \sum Sigma </tex>. ГоворятТребуется найти такую строку <tex>z</tex> максимальной длины, что <tex>z</tex> является и подстрокой <tex>s</tex>, и подстрокой <tex>t</tex>.}}{{Определение|definition = Будем говорить, что строка <tex>z[0 \, \ldots \, m-1 .. m]</tex> является подстрокой строки <tex>s[0 \, \ldots \, n-1 .. n]</tex>, если существует такой индекс <tex>k \in [0 .. \, \ldots \, n - m]</tex>, что для любого <tex>i \in [0 \, \ldots \, m-1 .. m]</tex> справедливо <tex>s[k + i] = z[i]</tex>. Требуется найти такую строку <tex>z</tex> максимальной длины, что <tex>z</tex> является и подстрокой <tex>s</tex>, и подстрокой <tex>t</tex>.}}

==Алгоритм==Данный алгоритм основывается на методе половинного деления. Пусть длина наибольшей общей подстроки будет <tex>x</tex>. Заметим, что у строк <tex>s</tex> и <tex>t</tex> обязательно найдется общая подстрока длины <tex>y \in [0 .. \ldots x]</tex>, так как в качестве такой строки можно взять префикс наибольшей общей подстроки. Рассмотрим функцию предикат <tex>f : \colon [0 .. \ldots \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>Предполагается, что хеширование будет проводится Хеширование будем производить так же, как и в [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа|алгоритме Рабина-Карпа]].

int findGCS(S<tex>i</tex> — длина подстроки, T)найденная с помощью [[Целочисленный двоичный поиск|двоичного поиска]].  n = min(len<tex>f(Si)</tex> — предикат, lenописанный в алгоритме.  '''bool''' f(T)i: '''int'''): hashes = хеши подстрок строки <tex>s</tex> длины <tex>i</tex> left '''for''' j = 0'''to''' |t| − i right hash = n hash(t[j ... j + i − 1]) '''if''' hash '''in''' hashes '''if''' совпали несколько случайных символов подстрок '''return''' ''true'' '''else''' '''continue''' while '''return''' ''false'' == Время работы ==Проведем оценку асимптотики времени работы предложенного алгоритма. Посмотрим, сколько нам потребуется действий на каждом шаге двоичного поиска. Во-первых, хеширование подстрок строки <tex>s</tex> и запись их в Set требует <tex>O(right |s|)</tex> шагов. Во- left вторых, хеширование подстрок строки <tex>t</tex> и проверка их наличия в Set требует <tex>O(|t|)</tex>. Проверка на совпадение нескольких символов подстрок требует константное время. Значит, на каждый шаг двоичного поиска требуется <tex> 1O(\max(|s|, |t|)): val = </tex> действий. Заметим, что всего для завершения двоичного поиска потребуется <tex>O(\log(\min(left + right|s|, |t|))) </ 2 if tex> шагов. Следовательно, суммарное время работы алгоритма будет <tex>O(\log(\min(f|s|, |t|)) \cdot \max(val|s|, |t|) == 1) left = val else right = val return left</tex> действий.

==Время работыСм. также ==Проведем оценку асимптотики времени работы предложенного алгоритма. Посмотрим сколько нам потребуется действий на каждом шаге бинарного поиска. Во-первых, хеширование подстрок строки <tex>s</tex> и запись их в Set требует <tex>O(|s|)</tex> шагов. Во-вторых, хеширование подстрок строки <tex>t</tex> и проверка их наличия в Set требует <tex>O(|t|)</tex>. В приведенных рассуждениях предполагается, что операции записи в Set и проверка наличия элемента в Set работают за амортизированную <tex>O(1)</tex>. Поскольку хешировали с помощью * [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа|этого]] метода, то это занимает линейное время. Значит,на каждый шаг бинарного поиска требуется <tex>O(max(|s|, |t|))</tex> действий. На самом деле требуется несколько больше времени, поскольку совпадение хешей не дает гарантии совпадения подстрок, однако чтобы это было справедливо с большой вероятностью, достаточно проверить совпадение лишь нескольких произвольных символов, вместо полной проверки. Тогда на это потребуется некоторое константное число операций, что маскируется с помощью <tex>O</tex>. Заметим, что всего для завершения бинарного поиска потребуется <tex>O(\log(\min(|s|, |t|)))</tex> шагов. Следовательно, суммарное время работы алгоритма будет <tex>O(\log(\min(|s|, |t|)) \times \max(|s|, |t|))</tex> действий.* [[Задача о наибольшей общей подпоследовательности]]

== Литература Источники информации ==* ''Кормен Т, Томас Х., Лейзерсон Ч, Чарльз И., Ривест Р, Рональд Л. , Штайн Клиффорд'' '''Алгоритмы: построение и анализ. — 2''', 3-е издиздание. Пер. с англ. — М.: Издательский дом «Вильямс»"Вильямс", 20072014. — С1328 с.: ил. — ISBN 978-5-8459-1794-2 (рус. 1296) — страницы 1036–1041.