Knuth-Morris-Pratt string search: Difference between revisions

<syntaxhighlight lang="11l">F kmp_table(String word) -> [Int]

print(‘Found `’word‘` in `’text[0.<10]‘...` ’number_of_positions‘ times at ’positions‘.’)</syntaxhighlight>

<pre>Found `TCTA` in `GCTAGCTCTA...` 2 times at [6, 14].

Found `alfalfa` in `Nearby far...` 2 times at [33, 87].</pre>

(if (= patPos M) (- textPos M) N ) ) ) )</syntaxhighlight>

end module kmp_mod</syntaxhighlight>

=={{header|FreeBASIC}}==

'''Adapted from [[#Wren|Wren]]'''

<syntaxhighlight lang="vb">Dim Shared As Integer t()

Dim Shared As Integer indices()

Sub Tabla(patron As String)

Dim As Integer nc = Len(patron)

Redim As Integer t(nc)

Dim As Integer idx = 1 ' index into table

Dim As Integer lon = 0 ' length of previous longest prefix

While idx < nc

If patron[idx] = patron[lon] Then

lon += 1

t(idx) = lon

idx += 1

Elseif lon <> 0 Then

lon = t(lon-1)

Else

t(idx) = 0

idx += 1

End If

Wend

End Sub

Sub BusquedaKMP(texto As String, patron As String)

Dim As Integer hc = Len(texto)

Dim As Integer nc = Len(patron)

Dim As Integer i = 0 ' index into haystack

Dim As Integer j = 0 ' index into needle

Dim As Integer cont = 1

Tabla(patron)

While i < hc

If patron[j] = texto[i] Then

i += 1

j += 1

End If

If j = nc Then

Redim Preserve indices(cont)

indices(cont) = (i - j)

cont += 1

j = t(j-1)

Elseif i < hc And patron[j] <> texto[i] Then

If j <> 0 Then j = t(j-1) Else i += 1

End If

Wend

End Sub

Dim As Integer i, j, k

Dim As String cadenas(1 To 6) = {"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."}

Dim As String palabra(1 To 7) = { _

"TCTA", "TAATAAA", "word", "needle", "put", "and", "alfalfa"}

For i = 1 To Ubound(cadenas)

Print Using "text# = &"; i; cadenas(i)

Next

Print

For i = 1 To Ubound(palabra)

j = Iif(i < 6, i, i-1)

Print Using "Found '&' in 'text#' at indices [ "; palabra(i); j;

BusquedaKMP(cadenas(j), palabra(i))

If Ubound(indices) > 0 Then

For k = 1 To Ubound(indices)

Print indices(k) & ", ";

Next

Else

Print " ";

End If

Print Chr(8) & Chr(8) & " ]"

Erase indices

Next

Sleep</syntaxhighlight>

{{out}}

<pre>text1 = GCTAGCTCTACGAGTCTA

text2 = GGCTATAATGCGTA

text3 = there would have been a time for such a word

text4 = needle need noodle needle

text5 = InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented

text6 = 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 'text1' at indices [ 6, 14 ]

Found 'TAATAAA' in 'text2' at indices [ ]

Found 'word' in 'text3' at indices [ 40 ]

Found 'needle' in 'text4' at indices [ 0, 19 ]

Found 'put' in 'text5' at indices [ 26, 90 ]

Found 'and' in 'text5' at indices [ 101, 128, 171 ]

Found 'alfalfa' in 'text6' at indices [ 33, 87 ]</pre>

=={{header|J}}==

<syntaxhighlight lang=jq># search for the string needle in the string haystack

tasks(texts; pats)</syntaxhighlight>

<pre>text1 = GCTAGCTCTACGAGTCTA

Found 'alfalfa' in text6 at indices [33, 87]</pre>

<pre>Found <put> at: (one-based indices) [27, 91]

Found <alfalfa> at: (one-based indices) [34, 88]</pre>

Found “alfalfa” in “Text6” at indices 33, 87.</pre>

<pre>Found `GCAGAGAG` in `GCATCGCAGAGAGTATACAGTACG` once at {6} (26 character comparisons)

Found `alfalfa` in `Nearby far... for milk. (114 characters)` twice at {34,88} (125 character comparisons)</pre>

<pre>Found `TCTA` in `GCTAGCTCTA...` 2 times at [6, 14].

Found `alfalfa` in `Nearby far...` 2 times at [33, 87].</pre>

<pre>text0 = GCTAGCTCTACGAGTCTA

Found 'alfalfa' in 'text6' at indices (33 87)</pre>

<pre>text0 = GCTAGCTCTACGAGTCTA

Found 'alfalfa' in 'text6' at indices [33, 87]</pre>

<pre>text1 = GCTAGCTCTACGAGTCTA

Found 'alfalfa' in 'text6' at indices [33, 87]</pre>