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

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

Псевдокод

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

Время работы

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

Оптимизация

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

• [math]\pi(i)[/math] превосходит [math]\pi(i-1)[/math] не больше чем на [math]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) + 1] = s[i][/math] ложно, то хотелось бы найти наибольшую длину [math]k[/math], для которой верно [math]\pi(i) = k[/math]. Когда мы найдем такое [math]k[/math] нам достаточно будет сравнить [math]s[k][/math] и [math]s[i][/math], при их равенстве [math]\pi(i) = k[/math] будет верно. Будем искать наше [math]k[/math] пока оно больше нуля, при равенстве нулю [math]\pi(i) = 1[/math], если [math]s[i] = s[1][/math], иначе нулю. Общая схема алгоритма у нас есть, теперь нужно только научиться искать [math]k[/math].
• Для поиска [math]k[/math] нам стоит использовать равенство [math]k = \pi(k - 1) + 1[/math], когда [math]s[k] = s[i][/math] ложно, взяв за исходное [math] k = \pi(i - 1) + 1[/math], это позволит выбирать [math]k[/math] по убыванию вплоть до нуля, так как очевидно, что [math]\pi(x) \geq \pi(\pi(x))[/math] для любых [math]x[/math].

Псевдокод

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

Время работы

В итоге мы получили алгоритм выполняющий [math]O(n)[/math] итераций за [math]O(1)[/math], что дает нам итоговое [math]O(n)[/math].

Литература

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