Изменения

Предложенная реализация имеет оценку по памяти <tex>O(P+T)</tex>. Оценки <tex>O(T)</tex> можно добиться за счет отказа от запоминания значений префикс-функции для позиций в <tex>S</tex>, меньших <tex>p + 1</tex> (т.е. до начала цепочки <tex>T</tex>), это . Это возможно из-за того, что мы точно знаем, что так как значение префикс функции не может превысить длину образца, благодаря разделительному символу <tex>\#</tex>.