Knuth-Morris-Pratt string search: Difference between revisions

=={{header|Emacs Lisp}}==

 

(defun kmp_compile_pattern (pattern)

"Compile pattern to DFA."

(if (= patPos M) (- textPos M) N ) ) ) )

 

=={{header|J}}==

 

j=. 0

T=. _1

end.

I. b

 

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

 

'alfalfa' kmp_search text2

 

(J uses index 0 for the first character in a sequence of characters.)

 

=={{header|Julia}}==

function kmp_table(W)

 

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]

 

=={{header|Phix}}==

<span style="color: #000080;font-style:italic;">--

-- demo\rosetta\KnuthMorrisPratt.exw

<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>

=={{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

if __name__ == "__main__":

main()

 

{{out}}

=={{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.

 

sub kmp_search (@S where *.Bool, @W where *.Bool) {

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>

=={{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

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}}