Алгоритм Кнута-Морриса-Пратта

2021-01-21T01:00:43Z

91.207.170.129: /* Оценка по памяти */ логическая ошибка и как следствие было неверное обоснование для оценки

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

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

[[Файл:kmp_pict2.png|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 .. tl - 1
'''if''' p[pl + i + 1] == pl
answer[count++] = i
'''return''' answer

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

==Оценка по памяти==
Предложенная реализация имеет оценку по памяти <tex>O(P+T)</tex>. Оценки <tex>O(P)</tex> можно добиться за счет запоминания значений префикс-функции для позиций в <tex>S</tex>, меньших <tex>|P| + 1</tex> (то есть до начала цепочки <tex>T</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.

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Поиск подстроки в строке]]
[[Категория:Точный поиск]]

Викиконспекты - Вклад участника [ru]

Алгоритм Кнута-Морриса-Пратта