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

Префикс-функция строки [math]s[/math] — функция [math]\pi(i) = max \{ k | k \lt i,[/math] [math]s[1..k] = s[i - k + 1..i] \}[/math].

Алгоритм

Наивный алгоритм вычисляет префикс функцию непосредственно по определению, сравнивая префиксы и суффиксы строк.

Псевдокод

Prefix_function ([math]s[/math])
     [math]\pi[/math][1..n] = 0
     for i = 1 to n
         for k = 1 to i - 1
             if s[1..k] == s[i - k + 1..i]
                 [math]\pi[/math][i] = k
     return [math]\pi[/math]

Пример

Рассмотрим строку abcabcd, для которой значение префикс-функции равно [math][0,0,0,1,2,3,0][/math].

Шаг	Строка	Значение функции
[math]1[/math]	a	0
[math]2[/math]	ab	0
[math]3[/math]	abc	0
[math]4[/math]	abca	1
[math]5[/math]	abcab	2
[math]6[/math]	abcabc	3
[math]7[/math]	abcabcd	0

Время работы

Всего [math]O(n^2)[/math] итераций цикла, на каждой из который происходит сравнение строк за [math]O(n)[/math], что дает в итоге [math]O(n^3)[/math].

Оптимизация

Вносятся несколько важных замечаний:

• Следует заметить, что [math]\pi(i) \le \pi(i-1) + 1[/math]. Действительно, если [math]\pi(i) \gt \pi(i-1) + 1[/math], тогда [math]\pi(i) - 1 \gt \pi(i-1)[/math], значит в [math]\pi(i-1)[/math] не максимально возможное значение, получено противоречие.
• Нужно избавиться от явных сравнений строк. Пусть вычислено [math]\pi(i-1)[/math] и [math]s[\pi(i-1) + 1] = s[i][/math], тогда [math]\pi(i) = \pi(i-1) + 1[/math]. Если [math]s[\pi(i) + 1] [/math] отличается от [math]s[i + 1][/math], то нужно найти наибольшую длину [math] k[/math], для которой верно [math]\pi(i) = k + 1[/math]. Когда найдется такое [math]k[/math] достаточно будет сравнить [math]s[k + 1][/math] и [math]s[i][/math], при их равенстве [math]\pi(i) = k + 1[/math] будет верно. Итеративно продолжается поиск [math]k[/math], пока оно больше нуля. Если [math]k=0[/math], то при [math]s[i] = s[1][/math] значение [math]\pi(i)=1[/math] , иначе нулю. Общая схема алгоритма есть, теперь нужно научиться искать [math]k[/math].
• За исходное [math]k[/math] нужно взять [math]\pi(i - 1)[/math], что следует из первого пункта. Как видно из рисунка, приведенного ниже, при совпадении символов [math]s[k + 1][/math] и [math]s[i][/math] длина наибольшего общего префикса увеличивается на единицу. В случае, когда символы [math]s[k+1][/math] и [math]s[i][/math] не совпадают, [math]\pi(k)[/math] — следующая по максимальности длина потенциального наибольшего общего префикса, что тоже понятно из рисунка. Последнее утверждение верно, пока [math]k\gt 0[/math], что позволит всегда найти его следующее значение.

Псевдокод

Prefix_function ([math]s[/math])
     [math]\pi[/math][1] = 0
     k = 0
     for i = 2 to n
         while k > 0 && s[i] != s[k + 1]
             k = [math]\pi[/math][k]
         if s[i] == s[k + 1]
             k++
         [math]\pi[/math][i] = k
     return [math]\pi[/math]

Время работы

Время работы алгоритма составит [math]O(n)[/math]. Для доказательства этого потребуется новое обозначение [math]w_i[/math] — количество итераций цикла [math]while[/math] на [math]i[/math]-ом шаге. Итоговое время работы алгоритма составит [math]\sum\limits_{i=2}^n w_i[/math]. Теперь стоит отметить, что [math]k[/math] увеличивается на каждом шаге не более чем на единицу, значит максимально возможное значение [math]k = n - 1.[/math] Внутри цикла [math]while[/math] значение [math]k[/math] лишь уменьшается, а из предыдущего утверждения получается, что оно не может уменьшиться больше, чем [math]n-1[/math] раз, значит [math]\sum\limits_{i=2}^n w_i \le n[/math], что дает итоговую оценку времени алгоритма [math]O(n)[/math].

Литература

Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.