304
правки
Изменения
→Алгоритм
==Алгоритм==
Наивный алгоритм вычисляет префикс функцию непосредственно по определению, сравнивая префиксы и суффиксы строк.
===Псевдокод===
'''Prefix_function''' (<tex>s</tex>)
<tex>\pi</tex>[1]=0
'''for''' i = 2 '''to''' n
'''for''' k = 1 '''to''' i - 1
'''if''' s[1..k] == s[i - k + 1..i]
<tex>\pi</tex>[i] = k
'''return''' <tex>\pi</tex>
===Пример===
Рассмотрим строку abcabcd, для которой значение префикс-функции равно <tex>[0,0,0,1,2,3,0]</tex>.
| <tex>7</tex> || abcabcd || 0
|}
===Время работы===
