Lyndon Words

A Lyndon word is a non-empty string that is strictly smaller than every one of its proper suffixes — equivalently, strictly smaller than all of its non-trivial rotations.

a, ab, aab, abb, aabab, abcbc are Lyndon. aa, aba, ba, abab are not.

Equivalent characterisations

$w <$ every proper suffix of $w$ .
$w <$ every non-trivial rotation of $w$ (so $w$ is the unique smallest rotation of itself, and is aperiodic).
$w$ is a single character, or $w = uv$ with $u, v$ Lyndon and $u < v$ (the standard factorisation).

The Chen-Fox-Lyndon theorem

Every string factors uniquely as $s = w_{1} w_{2} \dots w_{k}$ with each $w_{i}$ Lyndon and $w_{1} \geq w_{2} \geq \dots \geq w_{k}$ .

Duval’s algorithm computes this factorisation in $O (n)$ time and $O (1)$ space.

What it is for

Smallest cyclic rotation

Run Duval on $s + s$ and take the factor that starts at a position $< n$ and would extend past it. This is the standard $O (n)$ , $O (1)$ -space method — a competitor to Booth’s algorithm with shorter code.

int leastRotation(string s) {
    s += s;
    int n = s.size(), i = 0, ans = 0;
    while (i < n / 2) {
        ans = i;
        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) i += j - k;
    }
    return ans;
}

De Bruijn sequences

The FKM algorithm (Fredricksen-Kessler-Maiorana): concatenate, in lexicographic order, every Lyndon word whose length divides $n$ . The result is a de Bruijn sequence $B (σ, n)$ — a cyclic string of length $σ^{n}$ containing every length- $n$ string exactly once.

This is a strikingly clean construction; the alternative is an Eulerian circuit in the de Bruijn graph.

Generating all Lyndon words

Duval’s generation algorithm produces every Lyndon word of length $\leq n$ in lexicographic order, in $O (1)$ amortized per word:

void generate(int n, int sigma) {
    vector<int> w = {0};                     // start with the smallest
    while (!w.empty()) {
        output(w);
        int m = w.size();
        while ((int)w.size() < n) w.push_back(w[w.size() - m]);   // repeat periodically
        while (!w.empty() && w.back() == sigma - 1) w.pop_back();
        if (!w.empty()) w.back()++;
    }
}

The runs theorem

Every maximal repetition (run) in a string has a Lyndon root — a Lyndon word whose length is the run’s period. That observation is what proves a string has fewer than $n$ runs and gives the $O (n)$ algorithm to find them all (Bannai et al., 2015).

Burrows-Wheeler transform

The bijective BWT is defined via the Lyndon factorisation, and Lyndon words are central to the theory of the ordinary BWT as well.

Counting Lyndon words

The number of Lyndon words of length exactly $n$ over an alphabet of size $σ$ is

$L_{σ} (n) = \frac{1}{n} \sum_{d ∣ n} μ (d) σ^{n / d},$

by Möbius inversion — the necklace-counting formula, restricted to aperiodic necklaces. This is the same $\sum_{d ∣ n} d L_{σ} (d) = σ^{n}$ identity that underlies the FKM construction.

Why competitive programmers should care

Three concrete payoffs:

Smallest rotation in $O (n)$ — a common subproblem when canonicalising cyclic strings.
Lexicographically smallest / largest problems, where the greedy structure of Lyndon factorisation gives the answer directly.
De Bruijn sequences, which appear in “find the code that opens the lock” style problems.

Beyond that, the border/period theory Lyndon words formalise is what makes prefix functions and periodicity arguments work.

whoashish's cp notes

Directory