Knuth-Morris-Pratt string search: Difference between revisions
Content added Content deleted
(added Raku programming solution) |
m (→{{header|Raku}}: insignificant changes) |
||
Line 391: | Line 391: | ||
<lang perl6># 20220810 Raku programming solution |
<lang perl6># 20220810 Raku programming solution |
||
sub kmp_search (@S,@W) { |
sub kmp_search (@S where *.Bool, @W where *.Bool) { |
||
sub kmp_table (@W) { |
sub kmp_table (@W where *.Bool) { |
||
loop (my ($pos,$cnd,@T) = 1,0,-1 ; $pos < @W.elems ; ($pos, $cnd)>> |
loop (my ($pos,$cnd,@T) = 1,0,-1 ; $pos < @W.elems ; ($pos, $cnd)>>++) { |
||
if @W[$pos] eq @W[$cnd] { |
if @W[$pos] eq @W[$cnd] { |
||
@T[$pos] = @T[$cnd] |
@T[$pos] = @T[$cnd] |
||
Line 406: | Line 406: | ||
} |
} |
||
my ($j,$k,@T) = 0,0, |kmp_table @W; |
return gather loop (my ($j,$k,@T) = 0,0, |kmp_table @W; $j < @S.elems; ) { |
||
return gather while $j < @S.elems { |
|||
if @W[$k] eq @S[$j] { |
if @W[$k] eq @S[$j] { |
||
($j, $k)>> |
($j, $k)>>++; |
||
if $k == @W.elems { |
if $k == @W.elems { |
||
take $j - $k; |
take $j - $k; |
||
Line 416: | Line 414: | ||
} |
} |
||
} else { |
} else { |
||
($j, $k)>> |
($j, $k)>>++ if ($k = @T[$k]) < 0 |
||
} |
} |
||
} |
} |