xii. Lyndon Words and Minimal Rotation

A Lyndon word is a non-empty string strictly smaller than every proper suffix (equivalently, than all its non-trivial rotations: it is the unique smallest rotation of itself and is aperiodic). a, ab, aab, abb, aabab, abcbc are Lyndon; aa, aba, ba, abab are not. Characterisations: (1) smaller than every proper suffix; (2) smaller than every non-trivial rotation; (3) a single letter, or $uv$ with $u<v$ both Lyndon (standard factorisation).

Chen–Fox–Lyndon: every string factors uniquely as $w_1{w}_2\cdots w_k$ with each $w_i$ Lyndon and $w_1\ge w_2\ge \cdots \ge w_k$; Duval computes it in $O(n)$ time and $O(1)$ space.

Use	How
smallest rotation (canonical form of a necklace / cyclic string / polygon)	Duval on $s+s$, or the two-pointer (Booth-style) scan; largest rotation: flip comparisons
de Bruijn sequence $B(\sigma ,n)$	FKM: concatenate in order the Lyndon words whose length divides $n$; alternative: Euler circuit in the de Bruijn graph (Euler Tours)
all Lyndon words of length $\le n$ in order	Duval’s generation, $O(1)$ amortised each
counting	$L_{\sigma }(n)=\frac{1}{n}{\sum }_{d\mid n}\mu (d){\sigma }^{n/d}$ (aperiodic necklaces, Burnside)
runs	every run has a Lyndon root: fewer than $n$ runs (Runs)
bijective BWT	defined via the Lyndon factorisation

Two "Booth's algorithms"

Booth’s least-rotation algorithm (1980) is unrelated to Booth’s multiplication algorithm for signed binary multiplication.

vector<string> duval(const string& s) {                     // Lyndon factorisation, non-increasing factors
    int n = sz(s), i = 0; vector<string> res;
    while (i < n) {
        int j = i + 1, k = i;
        while (j < n && s[k] <= s[j]) { k = s[k] < s[j] ? i : k + 1; j++; }
        while (i <= k) { res.push_back(s.substr(i, j - k)); i += j - k; }
    }
    return res;
}
int leastRotationDuval(string s) {                          // start index of the smallest rotation (smallest index on ties)
    int n = sz(s); s += s; int i = 0, ans = 0;
    while (i < n) {
        ans = i; int j = i + 1, k = i;
        while (j < 2 * n && s[k] <= s[j]) { k = s[k] < s[j] ? i : k + 1; j++; }
        while (i <= k) i += j - k;
    }
    return ans;
}
int leastRotationTwoPointer(const string& s) {              // Booth-style two pointers, O(n)
    int n = sz(s), i = 0, j = 1, k = 0;
    while (i < n && j < n && k < n) {
        char a = s[(i + k) % n], b = s[(j + k) % n];
        if (a == b) { k++; continue; }
        if (a > b) i += k + 1; else j += k + 1;
        if (i == j) j++;
        k = 0;
    }
    return min(i, j);
}
bool isLyndon(const string& s) { auto f = duval(s); return sz(f) == 1; }
vector<vector<int>> lyndonWords(int n, int sigma) {         // all Lyndon words of length <= n, lexicographic
    vector<vector<int>> res; vector<int> w = {0};
    while (!w.empty()) {
        res.push_back(w); int m = sz(w);
        while (sz(w) < n) w.push_back(w[sz(w) - m]);        // repeat periodically
        while (!w.empty() && w.back() == sigma - 1) w.pop_back();
        if (!w.empty()) w.back()++;
    }
    return res;
}
vector<int> deBruijn(int sigma, int n) {                    // cyclic sequence of length sigma^n containing every word once (FKM)
    vector<int> seq;
    for (auto& w : lyndonWords(n, sigma)) if (n % sz(w) == 0) seq.insert(seq.end(), all(w));
    return seq;
}

Proof: Duval, the rotation algorithms, generation and FKM

Duval’s invariant: at the start of the inner loop and after each step, $s[i..j)=w^t{w}^{\prime }$ with $w=s[i..i+p)$ Lyndon, $p=j-k$, $t\ge 1$ and $w^{\prime }$ a proper prefix of $w$. If $s_j=s_k$ the periodic pattern continues; if $s_j>s_k$, the whole $s[i..j]$ is Lyndon (a standard lemma: $w^t{w}^{\prime }c$ with $c$ larger than the next character of $w$ is smaller than all its suffixes), so $p$ becomes $j+1-i$ ($k=i$); if $s_j<s_k$, no Lyndon factor starting at $i$ can extend past the copies of $w$, so the $t$ copies of $w$ are the next factors (they are the longest Lyndon prefixes by the minimality argument), and the scan resumes at $w^{\prime }$. Each character is compared $O(1)$ times amortised ($i$ advances by at least $j-k$ and the restart rescans at most $p$ characters), so $O(n)$. Uniqueness of the factorisation: the first factor must be the longest Lyndon prefix (a Lyndon word $uv$ with $u$ a factor would contradict non-increasing order).

Smallest rotation via Duval: in the factorisation of $ss$, the last factor starting before position $n$ is the start of the smallest rotation: the factors are non-increasing, so the suffix starting there is the smallest among suffixes starting before $n$ that are long enough, i.e. among the rotations. Two pointers: if the rotations at $i$ and $j$ agree on $k$ characters and then $s_{i+k}>s_{j+k}$, every rotation starting at $i+t$ ($0\le t\le k$) is beaten by the rotation at $j+t$, so they are discarded; the answer is never discarded and each step advances $i+j+k$, so $O(n)$.

Generation: the successor of a Lyndon word $w$ (of length $\le n$) in lexicographic order among Lyndon words of length $\le n$ is obtained by repeating $w$ periodically to length $n$, removing trailing maximal letters, and incrementing the last letter (Duval 1988; each prefix of a periodic extension of a Lyndon word that ends with an increased letter is Lyndon). FKM: the concatenation of the Lyndon words of length dividing $n$ in lexicographic order is a de Bruijn sequence (Fredricksen–Maiorana); its length is ${\sum }_{d\mid n}dL(d)={\sigma }^n$. Counting: each word of length $n$ is a power $u^{n/d}$ of a primitive word of length $d\mid n$, whose $d$ rotations are distinct and contain exactly one Lyndon word, so ${\sigma }^n={\sum }_{d\mid n}dL(d)$, and Möbius inversion gives the formula. Verified: factorisations against a brute-force check, rotations against brute force, the generator against exhaustive enumeration, de Bruijn sequences by checking every window.

Related notes

• Runs and Periodicity
• Burnside and Pólya (necklaces)
• Burrows–Wheeler