[Править]Пример использования

Строка	a	b	b	a	b
-функция	0	0	0	1	2

Состояние	1	2	3	4	5	6
Переходы по a	2	2	2	5	2	2
Переходы по b	1	3	4	1	6	4

Префикс-функция, построение автомата поиска подстрок с ее использованием (см. вики-конспекты)

Префикс-функция (англ. prefix-function) от строки — массив длин наибольших бордеров для каждой позиции этой строки

Здесь и далее считаем, что символы в строках нумеруются с .

Определим префикс-функцию от строки в позиции следующим образом: . Если мы не нашли такого , то

Наивный алгоритм вычисляет префикс-функцию непосредственно по определению, сравнивая префиксы и суффиксы строк. Обозначим длину строки за . Будем считать, что префикс-функция хранится в массиве .

[Править]Псевдокод

int[] prefixFunction(string s):

int[] p = int[s.length]

fill(p, 0)

for i = 1 to n

for k = 1 to i

if s[1..k] == s[i - k + 1..i]

p[i] = k

return p

[Править]Пример

Рассмотрим строку , для которой значение префикс-функции равно .

Шаг	Строка	Значение функции
	a	0
	ab	0
	abc	0
	abca	1
	abcab	2
	abcabc	3
	abcabcd	0

[Править]Время работы

Всего итераций цикла, на каждой из который происходит сравнение строк за , что дает в итоге .

[Править]Эффективный алгоритм

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

Заметим, что . Чтобы показать это, рассмотрим суффикс,оканчивающийся на позиции и имеющий длину , удалив из него последний символ, мы получим суффикс, оканчивающийся на позиции и имеющий длину , следовательно неравенство неверно.
Избавимся от явных сравнений строк. Пусть мы вычислили , тогда, если , то . Если окажется, что , то нужно попытаться попробовать подстроку меньшей длины. Хотелось бы сразу перейти к такому бордеру наибольшей длины, для этого подберем такое , что . Делаем это следующим образом. За исходное необходимо взять , что следует из первого пункта. В случае, когда символы и не совпадают, — следующее потенциальное наибольшее значение , что видно из рисунка. Последнее утверждение верно, пока , что позволит всегда найти его следующее значение. Если , то при , иначе .