Factorize string into Lyndon words: Difference between revisions
Factorize string into Lyndon words (view source)
Revision as of 19:33, 28 February 2024
, 2 months agoNew post.
m (→{{header|Julia}}: cleanup) |
(New post.) |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 161:
.
while i <= k
print substr s$ i (j - k)
i += j - k
.
Line 178:
lyndonfact m$
</syntaxhighlight>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.List;
public class FactorizeStringIntoLyndonWords {
public static void main(String[] args) {
// Create a 128 character Thue-Morse word
String thueMorse = "0";
for ( int i = 0; i < 7; i++ ) {
String thueMorseCopy = thueMorse;
thueMorse = thueMorse.replace("0", "a");
thueMorse = thueMorse.replace("1", "0");
thueMorse = thueMorse.replace("a", "1");
thueMorse = thueMorseCopy + thueMorse;
}
System.out.println("The Thue-Morse word to be factorised:");
System.out.println(thueMorse);
System.out.println();
System.out.println("The factors are:");
for ( String factor : duval(thueMorse) ) {
System.out.println(factor);
}
}
// Duval's algorithm
private static List<String> duval(String text) {
List<String> factorisation = new ArrayList<String>();
int i = 0;
while ( i < text.length() ) {
int j = i + 1;
int k = i;
while ( j < text.length() && text.charAt(k) <= text.charAt(j) ) {
if ( text.charAt(k) < text.charAt(j) ) {
k = i;
} else {
k += 1;
}
j += 1;
}
while ( i <= k ) {
factorisation.addLast(text.substring(i, i + j - k));
i += j - k;
}
}
return factorisation;
}
}
</syntaxhighlight>
<pre>
The Thue-Morse word to be factorised:
01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001
The factors are:
011
01
0011
00101101
0010110011010011
00101100110100101101001100101101
001011001101001011010011001011001101001100101101
001011001101
</pre>
=={{header|jq}}==
Line 398 ⟶ 471:
['011', '01', '0011', '00101101', '0010110011010011', '00101100110100101101001100101101', '001011001101001011010011001011001101001100101101', '001011001101', '001']
</syntaxhighlight>
=={{header|Raku}}==
{{trans|Julia}}
<syntaxhighlight lang="raku" line># 20240213 Raku programming solution
sub chenfoxlyndonfactorization(Str $s) {
my ($n, $i, @factorization) = $s.chars, 1;
while $i <= $n {
my ($j, $k) = $i X+ (1, 0);
while $j <= $n && substr($s, $k-1, 1) <= substr($s, $j-1, 1) {
substr($s, $k-1, 1) < substr($s, $j++ -1, 1) ?? ( $k = $i ) !! $k++;
}
while $i <= $k {
@factorization.push: substr($s, $i-1, $j-$k);
$i += $j - $k
}
}
die unless $s eq [~] @factorization;
return @factorization
}
my $m = "0";
for ^7 { $m ~= $m.trans('0' => '1', '1' => '0') }
say chenfoxlyndonfactorization($m);</syntaxhighlight>
{{out}} Same as Julia example.
You may [https://ato.pxeger.com/run?1=fVJNToNAFE5ccoqvDSlMoA2sNGJt7-DGxGhCKYRpy6AzQ7Q27UXcdKGX8jS-4SeWxshiwrz3_b3J-_iU8bo6Hr8qnY2vvi_mqlogyVORlW-brViWIosTXUr-HmteCvdOS9iKYWcBKLZwbeHD5j7mPRzDlGCTJI-l8hFGBv2a801KWNxQTzQKnciKRNY1iePegxv6CFjUIlriqiWORqCQSkvXVoY2JnDITPO0vGrLnQ19f7L6JM9D25jN4BKsicQwGNDF87pI-360Zqb1qVn_PSbPlcqve17cGFFMmjv6pZGUNzWzjknv1Kw-ljxFJTapUvS6SF_wcHg8c6q1ZKorKc461t6y6LHtgmYaBsPIykqJp0vsTOlApsVEy1go1wkcTG_hhI5vjvo_cBhFUPH2v-WwCxY1i9TuU7dXPw Attempt This Online!]
=={{header|RPL}}==
| |||