Pointer Walk

String Search

Naive, KMP, Boyer-Moore and Rabin-Karp look for one word in the same sentence. One of them reads the pattern backwards and skips most of the text.

AlgorithmsIntermediate12 min read

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.

Naive · ordinary textInteractive
Algorithm
Text
HERE␣IS␣A␣SIMPLE␣EXAMPLE
EXAMPLE

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.

Naive · ordinary textInteractive
HERE␣IS␣A␣SIMPLE␣EXAMPLE
EXAMPLE

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.

python
def find(text, pattern):
    for start in range(len(text) - len(pattern) + 1):
        if text[start:start + len(pattern)] == pattern:
            return start
    return -1

Its 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.

Naive · repetitive textInteractive
AAAAAAAAAAAAAAAB
AAAAB

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.

KMP · repetitive textInteractive
AAAAAAAAAAAAAAAB
AAAAB

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.

  1. Look at the text letter under the pattern's last position

    Compare from there, moving left.

  2. 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.

  3. If it does appear, line it up

    Slide the pattern until its copy of that letter sits under the text letter.

Boyer-Moore · ordinary textInteractive
HERE␣IS␣A␣SIMPLE␣EXAMPLE
EXAMPLE

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.

Rabin-Karp · ordinary textInteractive
HERE␣IS␣A␣SIMPLE␣EXAMPLE
EXAMPLE

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

Letters compared · ordinary textInteractive
27
Naive
27
KMP
15
Boyer-Moore
7
Rabin-Karp

Finding EXAMPLE in HERE IS A SIMPLE EXAMPLE. Lower is better.

Letters compared · repetitive textInteractive
60
Naive
27
KMP
16
Boyer-Moore
5
Rabin-Karp

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?

SituationChoice
Everyday codeYour language's built-in search. It is already well tuned
One pattern, long ordinary textBoyer-Moore or a relative
Text or pattern with lots of repetition, or a streaming input you cannot go back inKMP
Many patterns at onceRabin-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.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    9 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress