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

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

Время работы

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

Оптимизация

В начале приводится псевдокод алгоритма, а затем его обоснование.

Псевдокод

Prefix_function ([math]s[/math])
     [math]\pi[/math] = 0
     for i = 2 to n
         k = [math]\pi[/math][i - 1] 
         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]\pi[/math] можно перечислить все префиксы длины [math] k[/math] [math]s_k[/math], которые являются истинными суффиксами заданного префикса длины [math]i[/math] [math]s_i[/math]. Введем обозначение [math] \pi ' [i] = (\pi[i], \pi^{2}[i], ..., \pi^{t}[i])[/math], где величина [math]\pi^{j}[i][/math] обозначает [math]j[/math]-ю итерацию префиксной функции, т.е. [math]\pi^{0}[i] = i[/math] и при [math] i \ge 1[/math] [math]\pi^{j}[i] = \pi[\pi^{j-1}[i]][/math]. Кроме того, понятно, что последовательность [math]\pi'[i][/math] обрывается, когда в ней будет достигнуто значение [math]\pi^t[i] = 0[/math]. {{Лемма |about= Лемма об итерации префиксной функции |statement= Пусть [math]s[/math] - строка длиной [math]n[/math] с префиксной функцией [math]\pi[/math]. Тогда для всех [math] i = 0,1,..,n[/math] имеем [math]\pi'[i] = (k : k \lt q[/math] и [math]s_k s_i[/math].

Время работы

С помощью метода потенциалов можно показать, что время работы [math]O(n)[/math]. Потенциал величины [math]k[/math] связывается с текущим ее значением в алгоритме. Начальное значение этого потенциала равно нулю. На каждой итерации цикла [math]while[/math] значение [math]k[/math] уменьшается, поскольку [math]\pi(k) \lt k[/math]. Однако в силу [math]\pi(k) \ge 0[/math] значение этой переменной не бывает отрицательным. Также значение [math]k[/math] изменяется не более чем на 1 внутри тела цикла [math]for[/math]. Поскольку перед входом в цикл выполняется [math] k \lt i[/math] и поскольку значение переменной [math]i[/math] увеличивается в каждой итерации цикла [math]for[/math], справедливость неравенства [math]k \lt i[/math] сохраняется (подтверждая тот факт, что соблюдается также неравенство [math]\pi(i) \lt i [/math]. Каждое выполнение тела цикла [math]while[/math] можно оплатить соответствующим уменьшение потенциальной функции, поскольку [math]\pi(k) \lt k [/math]. Кроме этого значение потенциальной функции возрастает не более чем на 1, из-за этого амортизированная стоимость тела цикла [math]for[/math] — [math]O(1)[/math]. Так как количество итераций [math]O(n)[/math], и поскольку конечное значение потенциальной функции по величине не меньше, чем ее начальное значение, полное время работы в наихудшем случае равно [math]O(n)[/math].

Литература

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