Knuth-Morris-Pratt string search: Difference between revisions
Content added Content deleted
(J) |
|||
Line 46: | Line 46: | ||
(if (= patPos M) (- textPos M) N ) ) ) ) |
(if (= patPos M) (- textPos M) N ) ) ) ) |
||
</lang> |
</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}}== |
=={{header|Julia}}== |