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