Knuth-Morris-Pratt string search: Difference between revisions
Content added Content deleted
m (→{{header|Raku}}: insignificant changes) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 5: | Line 5: | ||
=={{header|Emacs Lisp}}== |
=={{header|Emacs Lisp}}== |
||
< |
<syntaxhighlight lang="lisp"> |
||
(defun kmp_compile_pattern (pattern) |
(defun kmp_compile_pattern (pattern) |
||
"Compile pattern to DFA." |
"Compile pattern to DFA." |
||
Line 45: | Line 45: | ||
(if (= patPos M) (- textPos M) N ) ) ) ) |
(if (= patPos M) (- textPos M) N ) ) ) ) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|J}}== |
=={{header|J}}== |
||
Implementation:< |
Implementation:<syntaxhighlight lang="j">kmp_table=: {{ |
||
j=. 0 |
j=. 0 |
||
T=. _1 |
T=. _1 |
||
Line 81: | Line 81: | ||
end. |
end. |
||
I. b |
I. b |
||
}}</ |
}}</syntaxhighlight> |
||
Task examples:< |
Task examples:<syntaxhighlight lang="j"> text1=: 'InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented' |
||
text2=: 'Nearby farms grew a half acre of alfalfa on the dairy''s behalf, with bales of all that alfalfa exchanged for milk.' |
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 |
'put' kmp_search text1 |
||
Line 92: | Line 92: | ||
'alfalfa' kmp_search text2 |
'alfalfa' kmp_search text2 |
||
33 87</ |
33 87</syntaxhighlight> |
||
(J uses index 0 for the first character in a sequence of characters.) |
(J uses index 0 for the first character in a sequence of characters.) |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="ruby">""" |
||
function kmp_table(W) |
function kmp_table(W) |
||
Line 173: | Line 173: | ||
println("Found <$pat2> at: (one-based indices) ", kmp_search(text1, pat2)) |
println("Found <$pat2> at: (one-based indices) ", kmp_search(text1, pat2)) |
||
println("Found <$pat3> at: (one-based indices) ", kmp_search(text2, pat3)) |
println("Found <$pat3> at: (one-based indices) ", kmp_search(text2, pat3)) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
Found <put> at: (one-based indices) [27, 91] |
Found <put> at: (one-based indices) [27, 91] |
||
Line 181: | Line 181: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #000080;font-style:italic;">-- |
<span style="color: #000080;font-style:italic;">-- |
||
-- demo\rosetta\KnuthMorrisPratt.exw |
-- demo\rosetta\KnuthMorrisPratt.exw |
||
Line 257: | Line 257: | ||
<span style="color: #000080;font-style:italic;">--KMP("aLfAlfa",farm) -- none |
<span style="color: #000080;font-style:italic;">--KMP("aLfAlfa",farm) -- none |
||
--KMP("aLfAlfa",farm,true) -- as -2</span> |
--KMP("aLfAlfa",farm,true) -- as -2</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
Significantly higher character comparison counts than [[Boyer-Moore_string_search#Phix]].<br> |
Significantly higher character comparison counts than [[Boyer-Moore_string_search#Phix]].<br> |
||
Line 274: | Line 274: | ||
=={{header|Python}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang="python">"""Knuth-Morris-Pratt string search. Requires Python >= 3.7.""" |
||
from typing import List |
from typing import List |
||
from typing import Tuple |
from typing import Tuple |
||
Line 374: | Line 374: | ||
if __name__ == "__main__": |
if __name__ == "__main__": |
||
main() |
main() |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 389: | Line 389: | ||
=={{header|Raku}}== |
=={{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. |
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. |
||
<lang |
<syntaxhighlight lang="raku" line># 20220810 Raku programming solution |
||
sub kmp_search (@S where *.Bool, @W where *.Bool) { |
sub kmp_search (@S where *.Bool, @W where *.Bool) { |
||
Line 437: | Line 437: | ||
my \j = $_ < 6 ?? $_ !! $_-1 ; # for searching text5 twice |
my \j = $_ < 6 ?? $_ !! $_-1 ; # for searching text5 twice |
||
say "Found '@pats[$_]' in 'text{j}' at indices ", kmp_search @texts[j].comb, @pats[$_].comb |
say "Found '@pats[$_]' in 'text{j}' at indices ", kmp_search @texts[j].comb, @pats[$_].comb |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 460: | Line 460: | ||
=={{header|Wren}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang="ecmascript">class KMP { |
||
static search(haystack, needle) { |
static search(haystack, needle) { |
||
haystack = haystack.bytes.toList |
haystack = haystack.bytes.toList |
||
Line 524: | Line 524: | ||
var j = (i < 5) ? i : i-1 |
var j = (i < 5) ? i : i-1 |
||
System.print("Found '%(pats[i])' in 'text%(j+1)' at indices %(KMP.search(texts[j], pats[i]))") |
System.print("Found '%(pats[i])' in 'text%(j+1)' at indices %(KMP.search(texts[j], pats[i]))") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |