Alternative Algorithms for Lyndon Factorization

Sukhpal Singh Ghuman, Emanuele Giaquinta, Jorma Tarhio

We present two variations of Duval's algorithm for computing the Lyndon factorization of a word. The first algorithm is designed for the case of small alphabets and is able to skip…