304
правки
Изменения
→Псевдокод
'''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>
==Время работы==
Всего <tex>O(n^2)</tex> итерация цикла, на каждой из который происходит сравнение строк за <tex>O(n)</tex>, что дает в итоге <tex>O(n^3)</tex>.
