Lyndon Factorization
Definition
We begin with the notion of the Lyndon factorization.
Lyndon word: a nonempty string \(s\) is called a simple string, or a Lyndon word, if it is strictly smaller in lexicographical order than every nonempty proper suffix of \(s\). For example, a, b, ab, aab, abb, ababb and abcd are all Lyndon words. A string \(s\) is a Lyndon word if and only if it is strictly smaller in lexicographical order than all of its nontrivial cyclic shifts (nontrivial: nonempty and different from the string itself).
Lyndon factorization: the Lyndon factorization of a string \(s\) is written \(s=w_1w_2\cdots w_k\), where every \(w_i\) is a simple string and the factors are in non-increasing lexicographical order, that is, \(w_1\ge w_2\ge\cdots\ge w_k\). Such a factorization always exists and is unique.
Duval's algorithm
Explanation
Duval's algorithm computes the Lyndon factorization of a string in \(O(n)\) time.
First we need one more notion. A string \(t\) that can be written as \(t=ww\cdots\overline{w}\), where \(w\) is a Lyndon word and \(\overline{w}\) is a prefix of \(w\) (possibly the empty string), is called a pre-simple string, or a pre-Lyndon word. A Lyndon word is also a pre-Lyndon word.
Duval's algorithm is greedy. While it runs, the string \(s\) is split into three parts \(s=s_1s_2s_3\): the Lyndon factorization of \(s_1\) has already been recorded, \(s_2\) is a pre-Lyndon word, and \(s_3\) is the part not yet processed.
Procedure
In outline, each step tries to append the first character of \(s_3\) to the end of \(s_2\). If \(s_2\) is then no longer a pre-Lyndon word, we cut a prefix off \(s_2\) (a piece of the Lyndon factorization) and attach it to the end of \(s_1\).
Now in more detail. Let a pointer \(i\) point to the first character of \(s_2\); it runs from \(1\) to \(n\) (the length of the string). Inside the loop, a second pointer \(j\) points to the first character of \(s_3\), and a pointer \(k\) points to the character of \(s_2\) under consideration (the character that corresponds to \(j\) in the previous period of \(s_2\)). We want to append \(s[j]\) to the end of \(s_2\), so we compare \(s[j]\) with \(s[k]\):
- If \(s[j]=s[k]\), appending \(s[j]\) to the end of \(s_2\) keeps it pre-simple. Just increment the pointers \(j\) and \(k\) (move each to the next position).
- If \(s[j]>s[k]\), then \(s_2s[j]\) becomes a Lyndon word. Increment \(j\) and point \(k\) at the first character of \(s_2\): now \(s_2\) is a new Lyndon word that consists of a single period.
- If \(s[j]<s[k]\), then \(s_2s[j]\) is not a pre-simple string, so we split one Lyndon substring off \(s_2\). Its length is \(j-k\), one period of \(s_2\). Then \(s_2\) becomes what is left after the split, and we repeat (note that the pointers \(j\) and \(k\) do not change in this case) until every period has been cut off. For the part that remains, simply roll back to its first character and continue from there.
Implementation
The code below returns the Lyndon factorization of a string \(s\).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | |
Complexity analysis
We now prove the complexity of the algorithm.
The outer loop runs at most \(n\) times, because \(i\) increases in every iteration. The second inner loop is also \(O(n)\), because it only records the Lyndon factorization. It remains to analyze the inner loop. The Lyndon word found in an iteration of the outer loop is longer than the leftover string we compared after it, so the leftover strings have total length less than \(n\) and the inner loop runs at most \(O(n)\) times. In fact the loops run at most \(4n-3\) times in total, and the time complexity is \(O(n)\).
Minimal string rotation
For a string \(s\) of length \(n\), the algorithm above also finds the minimal string rotation.
Build the Lyndon factorization of the string \(ss\) and look in it for a Lyndon word \(t\) that starts at a position less than \(n\) and ends at a position greater than or equal to \(n\). The properties of the Lyndon factorization make it easy to prove that the first character of the substring \(t\) is the first character of the minimal string rotation of \(s\): the \(n\) characters from the start of \(t\) onward form the minimal string rotation of \(s\).
So it is enough to record, during the factorization, where each pre-Lyndon word begins.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | |
Practice problems
-
This page is mainly translated from the blog post Декомпозиция Линдона. Алгоритм Дюваля. Нахождение наименьшего циклического сдвига and its English translation Lyndon factorization. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0.
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: sshwy, StudyingFather, orzAtalod, Xeonacid, 24OI-bot, hqztrue, Ir1d, ksyx, Enter-tainer, diauweb, iamtwz, Junyan721113, Soresen, Menci, shawlleyw, gi-b716, Tiphereth-A, Plastic-time (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.