Knuth-Morris-Pratt string search: Difference between revisions
m
syntax highlighting fixup automation
m (→{{header|Raku}}: insignificant changes) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 5:
=={{header|Emacs Lisp}}==
<
(defun kmp_compile_pattern (pattern)
"Compile pattern to DFA."
Line 45:
(if (= patPos M) (- textPos M) N ) ) ) )
</syntaxhighlight>
=={{header|J}}==
Implementation:<
j=. 0
T=. _1
Line 81:
end.
I. b
}}</
Task examples:<
text2=: 'Nearby farms grew a half acre of alfalfa on the dairy''s behalf, with bales of all that alfalfa exchanged for milk.'
'put' kmp_search text1
Line 92:
'alfalfa' kmp_search text2
33 87</
(J uses index 0 for the first character in a sequence of characters.)
=={{header|Julia}}==
<
function kmp_table(W)
Line 173:
println("Found <$pat2> at: (one-based indices) ", kmp_search(text1, pat2))
println("Found <$pat3> at: (one-based indices) ", kmp_search(text2, pat3))
</
<pre>
Found <put> at: (one-based indices) [27, 91]
Line 181:
=={{header|Phix}}==
<!--<
<span style="color: #000080;font-style:italic;">--
-- demo\rosetta\KnuthMorrisPratt.exw
Line 257:
<span style="color: #000080;font-style:italic;">--KMP("aLfAlfa",farm) -- none
--KMP("aLfAlfa",farm,true) -- as -2</span>
<!--</
{{out}}
Significantly higher character comparison counts than [[Boyer-Moore_string_search#Phix]].<br>
Line 274:
=={{header|Python}}==
Based on pseudocode found in the [https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm Wikipedia article]. Uses test cases from the [[#Wren]] solution.
<
from typing import List
from typing import Tuple
Line 374:
if __name__ == "__main__":
main()
</syntaxhighlight>
{{out}}
Line 389:
=={{header|Raku}}==
Based on pseudocode found in WP ([https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm#Description_of_pseudocode_for_the_search_algorithm kmp_search ] & [https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm#Description_of_pseudocode_for_the_table-building_algorithm kmp_table]). Data and output format mostly follows the Wren entry.
<syntaxhighlight lang="raku"
sub kmp_search (@S where *.Bool, @W where *.Bool) {
Line 437:
my \j = $_ < 6 ?? $_ !! $_-1 ; # for searching text5 twice
say "Found '@pats[$_]' in 'text{j}' at indices ", kmp_search @texts[j].comb, @pats[$_].comb
}</
{{out}}
<pre>
Line 460:
=={{header|Wren}}==
This is based on the code [https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/ here]. The examples used are the same as in the [[Boyer-Moore_string_search#Wren]] task.
<
static search(haystack, needle) {
haystack = haystack.bytes.toList
Line 524:
var j = (i < 5) ? i : i-1
System.print("Found '%(pats[i])' in 'text%(j+1)' at indices %(KMP.search(texts[j], pats[i]))")
}</
{{out}}
|