Duval Lyndon Factorization

A string is called a Lyndon word if it is strictly lexicographically smaller than all of its nontrivial cyclic rotations. Equivalently, a nonempty Lyndon word is strictly smaller than every proper suffix of itself. Any string can be uniquely factored into a sequence of Lyndon words s = w_1 w_2 ... w_k such that each w_i is a Lyndon word and the sequence is nonincreasing lexicographically: w_1 >= w_2 >= ... >= w_k. This unique decomposition is known as the Lyndon factorization of the string.

Experiment

You can interact with the algorithm using the Duval Lyndon Factorization module.

1. Select Mixed from the Text native select control.
2. Observe the visual trace showing the linear-time Duval i/j/k comparisons as it factors the text into "abac", "ab", and "a".
3. Check the resulting output cards to see the correct Factors, Factor count, and Longest factor length.