7
правок
Изменения
добавлено замечание
==Оценка по памяти==
Предложенная реализация имеет оценку по памяти <tex>O(P+T)</tex>. Оценки <tex>O(P)</tex> можно добиться за счет отказа от запоминания значений префикс-функции для позиций в <tex>S</tex>, меньших <tex>|P| + 1</tex> (то есть до начала цепочки <tex>T</tex>). Это возможно, так как значение префикс функции не может превысить длину образца, благодаря разделительному символу <tex>\#</tex>.
==Замечание==
Вместо [[Префикс-функция|префикс-функции]] в алгоритме Кнута-Морриса-Пратта можно использовать Z-функцию. Оценки времени работы и памяти при этом не изменятся.
==См. также==
