Knuth-Morris-Pratt string search: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) (Added Perl) |
|||
Line 179: | Line 179: | ||
Found <alfalfa> at: (one-based indices) [34, 88] |
Found <alfalfa> at: (one-based indices) [34, 88] |
||
</pre> |
</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}}== |
=={{header|Phix}}== |