Knuth-Morris-Pratt string search: Difference between revisions
Added Perl
SqrtNegInf (talk | contribs) (Added Perl) |
|||
Line 179:
Found <alfalfa> at: (one-based indices) [34, 88]
</pre>
=={{header|Perl}}==
{{trans|Raku}}
<syntaxhighlight lang="perl" line>use v5.36;
sub kmp_search ($S, $W) {
my @S = split '', $S;
my @W = split '', $W;
sub kmp_table (@W) {
my($pos,$cnd,@T) = (1,0,-1);
for (; $pos < @W ; $pos++, $cnd++) {
if ($W[$pos] eq $W[$cnd]) {
$T[$pos] = $T[$cnd]
} else {
$T[$pos] = $cnd;
while ($cnd >= 0 and $W[$pos] ne $W[$cnd]) { $cnd = $T[$cnd] }
}
}
$T[$pos] = $cnd;
@T
}
my @I;
my ($k,@T) = (0,kmp_table @W);
for (my $j=0; $j < @S;) {
if ($W[$k] eq $S[$j]) {
$j++; $k++;
if ($k == @W) {
push @I, $j - $k;
$k = $T[$k]
}
} else {
($j++, $k++) if ($k = $T[$k]) < 0
}
}
@I
}
my @texts = (
"GCTAGCTCTACGAGTCTA",
"GGCTATAATGCGTA",
"there would have been a time for such a word",
"needle need noodle needle",
"InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented",
"Nearby farms grew a half acre of alfalfa on the dairy's behalf, with bales of all that alfalfa exchanged for milk.",
);
my @pats = <TCTA TAATAAA word needle put and alfalfa>;
say "text$_ = $texts[$_]" for 0..$#texts;
say '';
for (0.. $#pats) {
my $j = $_ < 5 ? $_ : $_-1 ; # for searching text4 twice
say "Found '$pats[$_]' in 'text$j' at indices " . join ', ', kmp_search($texts[$j],$pats[$_]);
}</syntaxhighlight>
{{out}}
<pre>text0 = GCTAGCTCTACGAGTCTA
text1 = GGCTATAATGCGTA
text2 = there would have been a time for such a word
text3 = needle need noodle needle
text4 = InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented
text5 = Nearby farms grew a half acre of alfalfa on the dairy's behalf, with bales of all that alfalfa exchanged for milk.
Found 'TCTA' in 'text0' at indices 6, 14
Found 'TAATAAA' in 'text1' at indices
Found 'word' in 'text2' at indices 40
Found 'needle' in 'text3' at indices 0, 19
Found 'put' in 'text4' at indices 26, 90
Found 'and' in 'text4' at indices 101, 128, 171
Found 'alfalfa' in 'text5' at indices 33, 87</pre>
=={{header|Phix}}==
| |||