Knuth-Morris-Pratt string search: Difference between revisions

Content added Content deleted
(Added 11l)
Line 2: Line 2:


[https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm < About Knuth-Morris-Pratt String Search Algorithm >]
[https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm < About Knuth-Morris-Pratt String Search Algorithm >]

=={{header|11l}}==
{{trans|Python}}

<syntaxhighlight lang="11l">
F kmp_table(String word) -> [Int]
V position = 1
V candidate = 0

V table = [0] * (word.len + 1)
table[0] = -1

L position < word.len
I word[position] == word[candidate]
table[position] = table[candidate]
E
table[position] = candidate
L candidate >= 0 & word[position] != word[candidate]
candidate = table[candidate]
position++
candidate++

table[position] = candidate
R table

F kmp_search(String text, word)
V text_position = 0
V word_position = 0

[Int] positions
V number_of_positions = 0
V table = kmp_table(word)

L text_position < text.len
I word[word_position] == text[text_position]
text_position++
word_position++
I word_position == word.len
positions.append(text_position - word_position)
number_of_positions++
word_position = table[word_position]
E
word_position = table[word_position]
I word_position < 0
text_position++
word_position++

R (positions, number_of_positions)

V TEST_CASES = [(‘GCTAGCTCTACGAGTCTA’, ‘TCTA’),
(‘GGCTATAATGCGTA’, ‘TAATAAA’),
(‘there would have been a time for such a word’, ‘word’),
(‘needle need noodle needle’, ‘needle’),
(‘InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesley’""
‘DKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeand’""
‘assemblylanguagestoillustratetheconceptsandalgorithmsastheyare’""
‘presented’, ‘put’),
(‘InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesley’""
‘DKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeand’""
‘assemblylanguagestoillustratetheconceptsandalgorithmsastheyare’""
‘presented’, ‘and’),
(‘Nearby farms grew a half acre of alfalfa on the dairy's behalf, ’""
‘with bales of all that alfalfa exchanged for milk.’, ‘alfalfa’)]

L(text, word) TEST_CASES
V (positions, number_of_positions) = kmp_search(text, word)

I number_of_positions == 0
print(‘`’word‘` not found in `’text[0.<10]‘...`’)
E I number_of_positions == 1
print(‘Found `’word‘` in `’text[0.<10]‘...` once at ’positions‘.’)
E
print(‘Found `’word‘` in `’text[0.<10]‘...` ’number_of_positions‘ times at ’positions‘.’)
</syntaxhighlight>

{{out}}
<pre>
Found `TCTA` in `GCTAGCTCTA...` 2 times at [6, 14].
`TAATAAA` not found in `GGCTATAATG...`
Found `word` in `there woul...` once at [40].
Found `needle` in `needle nee...` 2 times at [0, 19].
Found `put` in `Inhisbooks...` 2 times at [26, 90].
Found `and` in `Inhisbooks...` 3 times at [101, 128, 171].
Found `alfalfa` in `Nearby far...` 2 times at [33, 87].
</pre>


=={{header|Emacs Lisp}}==
=={{header|Emacs Lisp}}==
Retrieved from "https://rosettacode.org/wiki/Knuth-Morris-Pratt_string_search"