Knuth-Morris-Pratt string search: Difference between revisions
Added 11l
Alextretyak (talk | contribs) (Added 11l) |
|||
Line 2:
[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}}==
| |||