Изменения

'''Алгоритм Кнута — Морриса — Пратта ''' (англ. ''Knuth–Morris–Pratt algorithm'') — алгоритм [[Наивный алгоритм поиска подстроки в строке#Постановка задачи|поиска подстроки в строке]].

Дана цепочка <tex>ST</tex> и образец <tex>TP</tex>. Требуется найти все позиции, начиная с которых <tex>TP</tex> входит в <tex>ST</tex>.

Построим строку <tex>S = P = T\#ST</tex>, где <tex>\#</tex> — любой символ, не входящий в алфавит <tex>SP</tex> и <tex>T</tex>. Посчитаем на ней значение [[Префикс-функция|префикс-функциюфункции]] <tex>\pi()p </tex>. Благодаря разделительному символу <tex>\#</tex>, выполняется <tex>\forall i: \pi(p[i) ] \le leqslant |TP|</tex>. Заметим, что по определению [[Префикс-функция|префикс-функции]] при <tex>i > |TP|</tex> и <tex>\pi(p[i) ] = |TP|</tex> подстроки длины <tex>TP</tex>, начинающиеся с позиций <tex>0</tex> и <tex>i - |TP| + 1</tex>, совпадают. Соберем все такие позиции <tex>i - |TP| + 1</tex> строки <tex>PS</tex>, вычтем из каждой позиции <tex>|TP| + 1</tex>, это и будет ответ.Другими словами, если в какой-то позиции <tex>i</tex> выполняется условие <tex>p[i]=|P|<br/tex>, то в этой позиции начинается очередное вхождение образца в цепочку.  [[Файл:kmp_pictkmp_pict2.png|500px640px]]

Пусть <tex>t '''int'''[] kmp('''string''' P, '''string''' T): '''int''' pl = P.length '''int''' tl = |T|</tex>, <tex>s .length '''int'''[] answer '''int'''[] p = [[Префикс-функция#Эффективный_алгоритм|S|</tex>.prefixFunction(P + "#" + T)]] '''int''' count = 0 '''for''' (i = 0 .. (s tl - 1)) '''if''' (<tex>\pi</tex>(t p[pl + i + 1) ] == t)pl answer[count++] = i + 1 - t '''return''' answer

Префикс-функция от строки <tex>O(s + t)S</tex> (время подсчета строится за <tex>\piO(S) = O(P + T)</tex> для . Проход цикла по строке <tex>P) + O(s)S</tex> (последующий содержит <tex>forO(T)</tex>) итераций. Итого, время работы алгоритма оценивается как <tex>= O(s P + tT)</tex>.

Предложенная реализация имеет оценку по памяти <tex>O(SP+T)</tex>. Оценки <tex>O(SP)</tex> можно добиться за счет незапоминания отказа от запоминания значений <tex>\pi()</tex> префикс-функции для позиций в <tex>PS</tex>, меньших <tex>t |P| + 1</tex> (то есть до начала цепочки <tex>ST</tex>). Это возможно, так как значение префикс-функции не может превысить длину образца, благодаря разделительному символу <tex>\#</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.

==Источники==[[Категория: Алгоритмы и структуры данных]][http[Категория://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm Knuth–Morris–Pratt algorithmПоиск подстроки в строке]]<br>Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн — Алгоритмы[[Категория: построение и анализ / пер. с англ. — изд. 2-е — М.: Издательский дом «Вильямс», 2009. — с.1036. — ISBN 978-5-8459-0857-5.Точный поиск]]