304
правки
Изменения
Нет описания правки
===Псевдокод===
'''Prefix_function''' (<tex>s</tex>)
<tex>\pi </tex> = 0
'''for''' i = 1 '''to''' n
'''for''' j = 1 '''to''' i - 1
'''if''' s[1..j] == s[i - j + 1..i]
<tex>\pi</tex>[i] = j '''return''' <tex>\pi</tex>
===Время работы===
===Псевдокод===
'''Prefix_function''' (<tex>s</tex>)
<tex>\pi </tex> = 0
'''for''' i = 2 '''to''' n
j = <tex>\pi</tex>[i - 1]
'''while''' j > 0 && s[i] != s[j + 1]
j = pi[j]
'''if''' s[i] == s[j + 1]
j++
<tex>\pi</tex>[i] = j '''return''' <tex>\pi</tex>
===Время работы===
В итоге мы получили алгоритм выполняющий <tex>O(n)</tex> итераций за <tex>O(1)</tex>, что дает нам итоговое <tex>O(n)</tex>.
