Изменения

Перейти к: навигация, поиск

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

1 байт добавлено, 20:31, 27 июня 2011
Нет описания правки
<tex>O(s + t)</tex> (время подсчета <tex>\pi()</tex> для <tex>P</tex>) + <tex>O(s)</tex> (последующий <tex>for</tex>) <tex>= O(s + t)</tex>.
*'''Оценка по памяти'''
Предложенная реализация имеет оценку по памяти <tex>O(S+T)</tex>. Оценки <tex>O(S)</tex> можно добиться за счет не запоминания значений <tex>\pi()</tex> для позиций в <tex>P</tex> меньших <tex>t + 1</tex> (т.е. до начала цепочки <tex>S</tex>)
108
правок

Навигация