Изменения

=='''Алгоритм Кнута — Морриса — Пратта''' (англ. ''Knuth–Morris–Pratt algorithm'') — алгоритм [[Наивный алгоритм поиска подстроки в строке#Постановка задачи==Дана цепочка <tex>S</tex> и образец <tex>T</tex>. Требуется найти все позиции, начиная с которых <tex>T</tex> входит |поиска подстроки в <tex>S</tex>строке]].

==Алгоритм решенияОписание алгоритма==Дана цепочка <tex>t = |T|; s = |S|; \$</tex> - любой символ, не входящий в алфавит и образец <tex>SP</tex> и . Требуется найти все позиции, начиная с которых <tex>TP</tex>*'''Псевдокод''' P <- входит в <tex>T</tex> + '$' + .<br>Построим строку <tex>S= P\#T</tex>; <вычисление префикс-функции для цепочки P> count <- 0 for (i = 0..s - 1) { if (, где <tex>\pi#</tex>(t + i + 1) = t) { answer[count] <- i + 1 - t count <- count + 1 } }*'''Корректность работы'''Отметим— любой символ, что из-за символа не входящий в алфавит <tex>\$P</tex> значение и <tex>\pi(k) \leq tT</tex> для всех . Посчитаем на ней значение [[Префикс-функция|префикс-функции]] <tex>kp </tex>.По определению Благодаря разделительному символу <tex>\pi()#</tex>, если выполняется <tex>\pi(k) = tforall i: p[i] \leqslant |P|</tex>. Заметим, то что по определению [[Префикс-функция|префикс-функции]] при <tex>i > |P|</tex> и <tex>p[0..t - 1i] = |P[k - t + 1..k]|</tex>, то есть подстроки длины <tex>T = S[k - t - t..k - t - 1]P</tex>, то есть начинающиеся с позиций <tex>T0</tex> входит в и <tex>Si - |P| + 1</tex>, начиная с совпадают. Соберем все такие позиции <tex>k i - t - t|P| + 1</tex>.Пусть теперь строки <tex>TS</tex> входит в , вычтем из каждой позиции <tex>S|P| + 1</tex>, начиная с это и будет ответ. Другими словами, если в какой-то позиции <tex>i</tex>. Тогда выполняется условие <tex>Sp[i]=|P|</tex>, то в этой позиции начинается очередное вхождение образца в цепочку.  [[Файл:kmp_pict2.i + t - 1png|640px]] ==Псевдокод== '''int'''[] kmp('''string''' P, '''string''' T): '''int''' pl = P.length '''int''' tl = T.length '''int'''[] answer '''int'''[] p = [[Префикс-функция#Эффективный_алгоритм|prefixFunction(P + "#" + T)]] '''int''' count = 0 '''for''' i = 0..t tl - 1 '''if''' p[pl + i + 1] == pl answer[count++]= i - pl '''return''' answer ==Время работы==Префикс-функция от строки <tex>S</tex>. Иными словами, строится за <tex>P[0..t - 1] O(S) = O(P[t + 1 + iT)</tex>..t + i + t]Проход цикла по строке <tex>S</tex> содержит <tex>O(T)</tex>итераций. Итого, что эквивалентно время работы алгоритма оценивается как <tex>\piO(t P + i + tT) = t</tex>.*'''Время работы'''==Оценка по памяти==Предложенная реализация имеет оценку по памяти <tex>O(s P+ tT)</tex>(время подсчета . Оценки <tex>\piO(P)</tex> можно добиться за счет запоминания значений префикс-функции для позиций в <tex>PS</tex>) + , меньших <tex>O(s)|P| + 1</tex>(последующий то есть до начала цепочки <tex>forT</tex>) . Это возможно, так как значение префикс-функции не может превысить длину образца, благодаря разделительному символу <tex>= O(s + t)\#</tex>. ==Замечание==Вместо [[Префикс-функция|префикс-функции]] в алгоритме Кнута-Морриса-Пратта можно использовать [[Z-функция|Z-функцию]]. Оценки времени работы и памяти при этом не изменятся. ==См. также==*[[Алгоритм Ахо-Корасик|Алгоритм Ахо-Корасик]]*[[Алгоритм Бойера-Мура|Алгоритм Бойера-Мура]]*[[Алгоритм Колусси|Алгоритм Колусси]]*[[Префикс-функция|Префикс-функция]]*[[Z-функция|Z-функция]] ==Источники информации==*[[wikipedia:en:Knuth–Morris–Pratt algorithm | Wikipedia {{---}} Knuth–Morris–Pratt algorithm]]*[[wikipedia:ru:Алгоритм Кнута — Морриса — Пратта | Википедия {{---}} Алгоритм Кнута — Морриса — Пратта]]*Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн — Алгоритмы: построение и анализ / пер. с англ. — изд. 2-е — М.: Издательский дом «Вильямс», 2009. — с.1036. — ISBN 978-5-8459-0857-5. [[Категория: Алгоритмы и структуры данных]][[Категория: Поиск подстроки в строке]][[Категория:Точный поиск]]