Find one word in a text
Press Ctrl+F in any document and the computer has to answer: where, in this long text, does this short pattern appear? Editors, search tools, virus scanners and DNA analysis all do the same thing at larger scale.
All four algorithms on this page slide the pattern along underneath the text and compare letters. They differ in how far they dare to jump after a mismatch. The score is the number of letter comparisons: fewer is better.
Start. Find "EXAMPLE" in the text. The pattern is slid along underneath, and every letter comparison is counted.
- Positions tried
- 0
- Letters compared
- 0
Naive
Try every position. Compare the pattern with the text from left to right. At the first mismatch, move the pattern one place along and start again.
Start. Find "EXAMPLE" in the text. The pattern is slid along underneath, and every letter comparison is counted.
- Positions tried
- 0
- Letters compared
- 0
It is easy to write and, on ordinary text, perfectly good: most positions fail on the very first letter.
def find(text, pattern):
for start in range(len(text) - len(pattern) + 1):
if text[start:start + len(pattern)] == pattern:
return start
return -1Its weak spot is repetitive text. Search for AAAAB in a long run of As and every position matches four letters before failing on the fifth. Then it moves one place and compares the same letters all over again.
Start. Find "AAAAB" in the text. The pattern is slid along underneath, and every letter comparison is counted.
- Positions tried
- 0
- Letters compared
- 0
KMP: never re-read the text
Knuth-Morris-Pratt notices that a mismatch after several matches is not wasted. Those matched letters tell you exactly what the text contains at that spot.
Example
What four matching A's tell you
The pattern is AAAAB. Four letters matched and the fifth did not. So the last four text letters were AAAA. Move the pattern one place and its first three letters are AAA, lined up with three text letters we already know are A. There is no need to compare them again. Continue from the letter that failed.
Before searching, KMP studies the pattern once and builds a small table: "after matching this many letters, how many can I keep?". With it, the text is read strictly left to right and no text letter is ever compared twice.
Start. Find "AAAAB" in the text. The pattern is slid along underneath, and every letter comparison is counted.
- Positions tried
- 0
- Letters compared
- 0
On this text KMP needs less than half the comparisons of the naive method. On ordinary English it does about the same work as the naive method, because long partial matches are rare. What KMP really gives you is a guarantee: its worst case is never bad.
Boyer-Moore: read the pattern backwards
Boyer-Moore compares from the last letter of the pattern to the first. That one change makes big jumps possible.
Look at the text letter under the pattern's last position
Compare from there, moving left.
On a mismatch, ask: where is that text letter in the pattern?
If it does not appear in the pattern at all, no position that covers it can match. Jump the pattern completely past it.
If it does appear, line it up
Slide the pattern until its copy of that letter sits under the text letter.
Start. Find "EXAMPLE" in the text. The pattern is slid along underneath, and every letter comparison is counted.
- Positions tried
- 0
- Letters compared
- 0
It found the word after trying 5 positions, where the naive method tried 18. Most of the text was never looked at. The longer the pattern, the bigger the jumps, which is why this family of algorithms is what fast search tools use on real text.
Rabin-Karp: compare numbers, not letters
Rabin-Karp turns the pattern into one number, a hash, and does the same for each window of text. Comparing two numbers is one step, however long the pattern is. Letters are compared only when the numbers agree.
The clever part is the rolling hash. Moving the window one place does not mean hashing it from scratch. Subtract the letter that left, add the letter that arrived.
Start. Find "EXAMPLE" in the text. The pattern is slid along underneath, and every letter comparison is counted.
- Positions tried
- 0
- Letters compared
- 0
Different text can produce the same number, so a match must still be confirmed letter by letter. With a good hash such false alarms are rare.
Its real strength is searching for many patterns at once: put all their hashes in a set and check each window's hash against the set in one step. Plagiarism checkers work this way.
The scores
Finding EXAMPLE in HERE IS A SIMPLE EXAMPLE. Lower is better.
Finding AAAAB in AAAAAAAAAAAAAAAB. Lower is better.
Rabin-Karp's bar is small because hash checks are not counted as letter comparisons: it still visits every position.
Which one should you use?
| Situation | Choice |
|---|---|
| Everyday code | Your language's built-in search. It is already well tuned |
| One pattern, long ordinary text | Boyer-Moore or a relative |
| Text or pattern with lots of repetition, or a streaming input you cannot go back in | KMP |
| Many patterns at once | Rabin-Karp |
Key takeaways
- String search slides a pattern along a text. The algorithms differ in how far they jump after a mismatch.
- Naive moves one place at a time. Fine on ordinary text, slow on repetitive text.
- KMP remembers what already matched and never re-reads a text letter.
- Boyer-Moore compares from the right and skips whole stretches of text.
- Rabin-Karp compares hashes and updates them cheaply as the window slides.