==Псевдокод==
'''Prefix_function''' (<tex>s</tex>)
<tex> pi \leftarrow = 0</tex> '''for''' <tex>i \leftarrow = 1</tex> '''to''' <tex>n</tex> '''for''' <tex>j \leftarrow = 1</tex> '''to''' <tex>i - 1</tex> '''if''' <tex>s[1..j] == s[i - j + 1..i]</tex> <tex> pi[i] \leftarrow = j</tex> '''return''' <tex>pi</tex>
==Время работы==
