File Lyndon.h
↰ Parent directory (ADS/string)
The Lyndon factorization and the least rotation of a string, beyond the book.
Definition (ADS/string/Lyndon.h)
Detailed Description
- A Lyndon word is a nonempty string strictly smaller than all its proper rotations (equivalently, than all its proper suffixes), and every string S has one factorization :math:`[
S = w_1 w_2 cdots w_k , qquad w_1 ge w_2 ge cdots ge w_k ,
` into Lyndon words (Chen, Fox and Lyndon).
lyndonFactorization() is the algorithm of Duval: it keeps S = s_1 s_2 s_3 with s_1 factored, :math:` s_2 = w^h w’ ` for a Lyndon word w and a proper prefix w’ of w, and compares the next character c of :math:` s_3 ` with the one |w| places before: if equal, w’ grows; if larger, :math:` s_2 c ` is a Lyndon word and becomes w; if smaller, the h copies of w are factors and the scan resumes after them. Each comparison either advances the scan or is followed by the output of a factor at least as long as the characters rescanned, so that the time is O( n ), in O( 1 ) space besides the factors.
leastRotation() gives the start of the lexicographically least rotation of S (the first one if several), by the same scan on S S: the least rotation starts at the start of the factor of S S that covers the place n, O( n ) time.
The contracts [see File Contract.h]: the factors are Lyndon words in non-increasing order that give S back (an audit), and the rotation is not larger than any other (an audit, :math:` O( n^2 ) `). The functions are defined in Lyndon.tpp.
Chen, R. H. Fox, R. C. Lyndon, Free differential calculus, IV. The quotient groups of the lower central series, Annals of Mathematics 68(1), 81-95, 1958, doi:10.2307/1970044
J.-P. Duval, Factorizing words over an ordered alphabet, Journal of Algorithms 4(4), 363-381, 1983, doi:10.1016/0196-6774(83)90017-2
- Donato Meoli
Dipartimento di Informatica Universita’ di Pisa
by Donato Meoli
Includes
ADS/Contract.h(File Contract.h)ADS/string/impl/Lyndon.tppcstddefstring_viewvector