Изменения
→Алгоритм Дюваля
==Алгоритм Дюваля==
Алгоритм Дюваля (англ. ''Duval's algorithm'') находит для данной строки длины <tex>n</tex> декомпозицию Линдона за время <tex>O(n)</tex> с использованием <tex>O(1)</tex> дополнительной памяти.
{{Определение
|id=def3
|definition='''Предпростая строка''' {{---}} строка <tex>s</tex>, такая что <tex>s = w + w + ... + w + w'</tex>, где <tex>w</tex> {{---}} некоторая простая строка, а <tex>w'</tex> - некоторый префикс строки <tex>w</tex>.
}}
string s // входная строка
string[] words // декомпозиция
n <tex>\leftarrow</tex> |s|
i <tex>\leftarrow</tex> 0
w <tex>\leftarrow</tex> 0
while (i < n) {
j <tex>\leftarrow</tex> i + 1
k <tex>\leftarrow</tex> i
while (j < n and s[k] <= s[j]) {
if s[k] < s[j]
k <tex>\leftarrow</tex> i
else
k <tex>\leftarrow</tex> k + 1
j <tex>\leftarrow</tex> j + 1
}
while (i <= k) {
words[w] <tex>\leftarrow</tex> s[i..j-k]
w <tex>\leftarrow</tex> w + 1
i <tex>\leftarrow</tex> i + j - k;
}
}
