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

Определение

Префикс-функцией цепочки [math]S[/math] называется функция [math]\pi(k) = max \{ j | j \leq k \& 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]\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 \& 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].