1632
правки
Изменения
м
*[[wikipedia:en:Knuth–Morris–Pratt algorithm | Wikipedia {{---}} Knuth–Morris–Pratt algorithm]]
rollbackEdits.php mass rollback
'''for''' i = 0 .. tl - 1
'''if''' p[pl + i + 1] == pl
answer[count++] = i- pl
'''return''' answer
==Оценка по памяти==
Предложенная реализация имеет оценку по памяти <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.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Поиск подстроки в строке]]
[[Категория:Точный поиск]]
