Префикс-функция

Определение

Префикс-функцией цепочки [math]S[/math] называется функция [math]\pi(k) = max \{ j | j \leq k[/math] [math]\&[/math] [math]s[0..j - 1] = s[k - j + 1..k] \}[/math]

Алгоритм вычисления

[math] n = |S|[/math]

• Псевдокод

 k = 0
 [math]\pi[/math](0) = 0
 for (i = 1 .. (n - 1)) {
   while (k > 0 && s[i] [math]\ne[/math] s[k])
     k = [math]\pi[/math](k - 1)
   if (s[i] == s[k])
     k = k + 1
   [math]\pi[/math](i) = k
 }

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

 Как видно из рисунка, при совпадении символов [math]S[k][/math] и [math]S[i][/math] длина наибольшего общего префикса увеличивается на 1. В случае, когда символы [math]S[k][/math] и [math]S[i][/math] не совпадают, [math]pi(k-1)[/math] - следующая по максимальности длина потенциального наибольшего общего префикса

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

 Сперва отметим очевидный из определения факт: [math]\pi(k + 1) - \pi(k) \leq 1[/math] для любого [math]k[/math]. В самом деле, в противном случае [math]\pi(k)[/math] не максимально.
 Теперь рассмотрим произвольную итерацию внешнего цикла [math]for[/math]. Возможно одно из трёх:
 1) [math]s[i] = s[k][/math]. Тогда значение [math]k[/math] увеличивается на 1, цикл [math]while[/math] не итерируется
 2) [math]k = 0[/math] [math]\&[/math] [math]s[i] \ne s[k][/math]. Тогда значение [math]k[/math] не изменяется, цикл [math]while[/math] не итерируется
 3) [math]while[/math] итерируется хотя бы раз. При каждой итерации [math]while[/math] значение [math]k[/math] может, очевидно, лишь уменьшаться, при этом, в силу отмеченного выше очевидного наблюдения, общее число итераций [math]while[/math] для всех итераций [math]for[/math] не превышает [math]n[/math]
 Таким образом, общее время работы - [math]O(n)[/math].