Изменения

Построим строку <tex>S = P\#T</tex>, где <tex>\#</tex> — любой символ, не входящий в алфавит <tex>P</tex> и <tex>T</tex>. Посчитаем на ней [[Префикс-функция|префикс-функцию]] <tex>\pi()</tex>. Благодаря разделительному символу <tex>\#</tex>, выполняется <tex>\forall i: \pi(i) \le leqslant |P|</tex>. Заметим, что по определению [[Префикс-функция|префикс-функции]] при <tex>i > |P|</tex> и <tex>\pi(i) = |P|</tex> подстроки длины <tex>P</tex>, начинающиеся с позиций <tex>0</tex> и <tex>i - |P| + 1</tex>, совпадают. Соберем все такие позиции <tex>i - |P| + 1</tex> строки <tex>S</tex>, вычтем из каждой позиции <tex>|P| + 1</tex>, это и будет ответ. Другими словами, если в какой-то позиции <tex>i, </tex> выполняется условие <tex>\pi(i)=|P|</tex>, то в этой позиции начинается очередное вхождение образца в цепочку.

Пусть <tex> '''int'''[] kmp('''string''' T, '''string''' P) '''int''' p = |P|</tex>, <tex>.length '''int''' t = |T|</tex>.length '''int'''[] answer count = 0 '''for''' (i = 0 .. (t - 1)) '''if''' (<tex>\pi</tex>(p + i + 1) == p) answer[count++] = i + 1 - p '''return''' answer

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