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

Материал из Викиконспекты
Перейти к: навигация, поиск

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