Knuth-Morris-Pratt string search: Difference between revisions
J
(J) |
|||
Line 46:
(if (= patPos M) (- textPos M) N ) ) ) )
</lang>
=={{header|J}}==
Implementation:<lang J>kmp_table=: {{
j=. 0
T=. _1
for_ch. }.y do.
if. ch=j{y do.
T=. T,j{T
else.
T=. T,j while. (0<:j) * ch~:j{y do. j=. j{T end.
end.
j=. j+1
end.
T=. T, j
}}
kmp_search=: {{
b=. 0#~#y
k=. _1
f=. _1+#x
T=. kmp_table x
for_ch. y do.
if. ch=x{~k=.k+1 do.
if. f=k do.
b=. 1 (ch_index-k)} b
k=. k{T
end.
else.
while. _1<k do.
if. ch=x{~k=. k{T do. break. end.
end.
end.
end.
I. b
}}</lang>
Task examples:<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.'
'put' kmp_search text1
26 90
'and' kmp_search text1
101 128 171
'and' kmp_search text2
'alfalfa' kmp_search text2
33 87</lang>
(J uses index 0 for the first character in a sequence of characters.)
=={{header|Julia}}==
| |||