3622
правки
Изменения
м
→Алгоритм Дюваля
==Алгоритм Дюваля==
===Алгоритм===
Алгоритм Дюваля (англ. ''Duval's algorithm'') находит для данной строки длины <tex>n</tex> декомпозицию Линдона за время <tex>O(n)</tex> с использованием <tex>O(1)</tex> дополнительной памяти. Он строит декомпозицию только на упорядоченных алфавитах. Алгоритм Дюваля относится к классу жадных алгоритмов.
{{Определение
|id=def3
|definition='''Предпростая строка''' {{---}} строка <tex>s</tex>, такая что <tex>s = ww...\dots ww'</tex>, где <tex>w</tex> {{---}} некоторая простая строка, а <tex>w'</tex> {{---}} некоторый префикс строки <tex>w</tex>.
}}
Во время работы алгоритма строка <tex>s</tex> разделена на три строки представлена в виде конкатенации трёх строк <tex>s = s_1s_2s_3</tex>, где в строке для строки <tex>s_1</tex> декомпозиция Линдона уже найдена, и <tex>s_1</tex> уже больше не используется алгоритмом; строка <tex>s_2</tex> {{---}} это предпростая строка (причём длину простых строк внутри неё мы также запоминаем); строка <tex>s_3</tex> {{---}} это ещё не обработанная алгоритмом часть строки <tex>s</tex>. Алгоритм Дюваля берёт первый символ строки <tex>s_3</tex> и пытается дописать его к строке <tex>s_2</tex>. При этом, возможно, для какого-то префикса строки <tex>s_2</tex> декомпозиция Линдона становится известной, и эта часть переходит к строке <tex>s_1</tex>.
Будем поддерживаться указатель <tex>i</tex> на начало строки <tex>s_2</tex>. Внешний цикл алгоритма будет выполняться, пока <tex>i < n</tex>, то есть пока вся строка <tex>s</tex> не перейдёт в строку <tex>s_1</tex>. Внутри этого цикла создаются два указателя: указатель <tex>j</tex> на начало строки <tex>s_3</tex> и указатель <tex>k</tex> на текущий символ в строке <tex>s_2</tex>, с которым будет производиться сравнение. Затем будем в цикле пытаться добавить символ <tex>s[j]</tex> к строке <tex>s_2</tex>, для чего необходимо произвести сравнение с символом <tex>s[k]</tex>. При этом будем поддерживать инвариант: <tex>j - k</tex> {{---}} длина подстроки w.
