Duval's Algorithm

Purpose: Compute the Lyndon factorisation of a string — its unique decomposition $s=w_1{w}_2\cdots w_k$ into non-increasing Lyndon words — in $O(n)$ time and $O(1)$ extra space.

Lyndon word

A non-empty string that is strictly smaller than all of its proper suffixes. Equivalently, strictly smaller than all of its non-trivial rotations. a, ab, aab, abb, aabab are Lyndon; aa, aba, ba are not.

Chen-Fox-Lyndon theorem: every string factors uniquely as $w_1\ge w_2\ge \cdots \ge w_k$ with each $w_i$ Lyndon.

Algorithm

Maintain a pointer $i$ to the start of the part not yet factorised. From $i$, run two pointers $j$ (the character being read) and $k$ (the character it is compared against, one period behind):

1. Start $j=i+1$, $k=i$.
2. While $j<n$:
   • if s[j] > s[k] → the candidate can still grow; reset $k=i$, advance $j$.
   • if s[j] == s[k] → still periodic; advance both $j$ and $k$.
   • if s[j] < s[k] → the Lyndon word ends; break.
3. The period is $p=j-k$. Emit $\lfloor (j-i)/p\rfloor$ copies of the Lyndon word s[i..i+p), advancing $i$ by $p$ each time, until $i>j-p$.
4. Repeat from step 1 with the new $i$.

Code

vector<string> duval(const string& s) {
    int n = s.size(), i = 0;
    vector<string> factorization;
    while (i < n) {
        int j = i + 1, k = i;
        while (j < n && s[k] <= s[j]) {
            if (s[k] < s[j]) k = i;   // grew: restart the period check
            else k++;                 // equal: continue the period
            j++;
        }
        while (i <= k) {              // emit whole periods
            factorization.push_back(s.substr(i, j - k));
            i += j - k;
        }
    }
    return factorization;
}

Paradigm

Greedy with amortized two pointers. Each character is examined a bounded number of times across the whole run.

Complexity

• Time: $O(n)$
• Space: $O(1)$ beyond the output

Why It Works

The inner loop finds the longest prefix of s[i..] that is a power of a Lyndon word: the invariant is that s[i..j) equals $w^t{w}^{\prime }$ where $w=$ s[i..i+p) is Lyndon, $p=j-k$, and $w^{\prime }$ is a proper prefix of $w$. When s[j] < s[k] the string can no longer be extended without breaking the Lyndon property, so the completed factors are exactly the $t$ copies of $w$. Uniqueness of the factorisation is the Chen-Fox-Lyndon theorem; greedy taking of the longest Lyndon prefix at each step is exactly what produces it. ∎

Variants / Use Cases

• Smallest cyclic rotation — run Duval on $s+s$ and stop at the factor that starts before position $n$; this is the standard alternative to Booth’s algorithm
• Largest cyclic rotation — same, with the comparison reversed
• Generating all Lyndon words of length ≤ n in lexicographic order (the FKM / Duval generation algorithm) — used to build de Bruijn sequences
• Burrows-Wheeler transform and bijective BWT — built on Lyndon factorisation
• Runs / periodicity theory — the “runs theorem” proof uses Lyndon roots
• Lyndon words — the theory page