Lyndon Words & Duval's Algorithm — Three-Pointer Factorization

A Lyndon word is strictly smaller than all its rotations. Watch Duval's i/j/k pointers scan the string and emit the non-increasing Lyndon factors. Switch to rotation mode to see the smallest cyclic rotation via s+s.

step 0

Scanning string

i — factor start j — look-ahead k — trailing (period) current candidate emitted factor

Running decomposition   w₁ ≥ w₂ ≥ …

Press Step to begin.
Duval scans once with three pointers. s[k] <= s[j] drives the loop: equal → advance k (period continues); s[k] < s[j] → reset k=i (candidate extends); s[k] > s[j] → emit Lyndon factors of length (j−k).
Self-contained visualization. The factorization is the unique Chen-Fox-Lyndon decomposition (non-increasing Lyndon words), computed in O(n) time and O(1) extra space. In rotation mode we run the same scan on s + s; the start of the last factor before the dashed midline marks the smallest cyclic rotation. See junior.md and professional.md for the proofs.