Factorize string into Lyndon words: Difference between revisions
Factorize string into Lyndon words (view source)
Revision as of 21:02, 31 January 2024
, 3 months agoAdded Algol 68
mNo edit summary |
(Added Algol 68) |
||
Line 15:
The Chen–Fox–Lyndon theorem states that any string is uniquely factorizable into a sequence of Lyndon words non-decreasing in lexicographic order. Duval's algorithm computes this in O(length of input) time and and O(1) space.<ref>Duval, Jean-Pierre (1983), "Factorizing words over an ordered alphabet", ''Journal of Algorithms'', '''4''' (4): 363–381, doi:10.1016/0196-6774(83)90017-2</ref> See <ref name=":0">https://cp-algorithms.com/string/lyndon_factorization.html</ref> for a description of Duval's algorithm.
=={{header|ALGOL 68}}==
{{Trans|Python|with multiline output as with a number of other samples}}
<syntaxhighlight lang="algol68">
BEGIN # Factorize a string into Lyndon words - translated of the Python sample #
PROC chen fox lyndon factorization = ( STRING s )[]STRING:
BEGIN
INT n = ( UPB s - LWB s ) + 1;
INT i := LWB s;
FLEX[ 1 : 100 ]STRING factorization;
INT f max := LWB factorization;
WHILE i <= n DO
INT j := i + 1, k := i;
WHILE IF j <= n THEN s[ k ] <= s[ j ] ELSE FALSE FI DO
IF s[ k ] < s[ j ] THEN
k := i
ELSE
k +:= 1
FI;
j +:= 1
OD;
WHILE i <= k DO
f max +:= 1;
IF f max > UPB factorization THEN
[ 1 : UPB factorization + 20 ]STRING new factorization;
new factorization[ 1 : UPB factorization ] := factorization;
factorization := new factorization
FI;
factorization[ f max ] := s[ i : i + j - k - 1 ];
i +:= j - k
OD
OD;
STRING check := "";
FOR i TO f max DO check +:= factorization[ i ] OD;
IF check /= s THEN print( ( "Incorrect factorization", newline ) ); stop FI;
factorization[ 1 : f max ]
END # chen fox lyndon factorization # ;
# Example use with Thue-Morse sequence #
STRING m := "0";
TO 7 DO
STRING m0 = m;
FOR i FROM LWB m TO UPB m DO
IF m[ i ] = "0" THEN m[ i ] := "1" ELIF m[ i ] = "1" THEN m[ i ] := "0" FI
OD;
m0 +=: m
OD;
[]STRING m factors = chen fox lyndon factorization( m );
FOR i FROM LWB m factors TO UPB m factors DO
print( ( m factors[ i ], newline ) )
OD
END
</syntaxhighlight>
{{out}}
<pre>
011
01
0011
00101101
0010110011010011
00101100110100101101001100101101
001011001101001011010011001011001101001100101101
001011001101
001
</pre>
== {{header|C++}} ==
| |||