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

Постановка задачи

Дана цепочка [math]S[/math] и образец [math]T[/math]. Требуется найти все позиции, начиная с которых [math]T[/math] входит в [math]S[/math].

Алгоритм решения

[math]t = |T|; s = |S|; \$[/math] - любой символ, не входящий в алфавит [math]S[/math] и [math]T[/math]

• Псевдокод

 P <- [math]T[/math] + '$' + [math]S[/math];
 <вычисление префикс-функции для цепочки P>
 count <- 0
 for (i <- 0 .. (s - 1)) {
   if ([math]\pi[/math](t + i + 1) = t) {
     answer[count] <- i + 1 - t
     count <- count + 1
   }
 }

• Корректность работы

Отметим, что из-за символа [math]\$[/math] значение [math]\pi(k) \leq t[/math] для всех [math]k[/math]. По определению [math]\pi()[/math], если [math]\pi(k) = t[/math], то [math]P[0..t - 1] = P[k - t + 1..k][/math], то есть [math]T = S[k - t - t..k - t - 1][/math], то есть [math]T[/math] входит в [math]S[/math], начиная с позиции [math]k - t - t[/math]. Пусть теперь [math]T[/math] входит в [math]S[/math], начиная с позиции [math]i[/math]. Тогда [math]S[i..i + t - 1] = T[0..t - 1][/math]. Иными словами, [math]P[0..t - 1] = P[t + 1 + i..t + i + t][/math], что эквивалентно [math]\pi(t + i + t) = t[/math].

• Время работы

[math]O(s + t)[/math](время подсчета [math]\pi()[/math] для [math]P[/math]) + [math]O(s)[/math](последующий [math]for[/math]) [math]= O(s + t)[/math].