How Ctrl+F Finds Text Instantly: KMP and String Matching Explained

You press Ctrl+F, type a word, and every match on a long page lights up before you have lifted your finger. It feels like magic, but the problem underneath is one of the oldest in computing: find a short piece of text, the pattern, inside a much longer piece, the text. A beginner solves it in ten lines. A careful engineer asks what happens when those ten lines meet a hostile input. This guide walks through the simple method, shows exactly where it breaks, and then explains the Knuth-Morris-Pratt algorithm, the idea that makes searching reliably fast. Every number in it comes from code I ran.

The problem: a needle in a haystack

Computer scientists call the long text the haystack and the thing you are looking for the needle. Searching a web page, a Word document, a source file or a chromosome all reduce to the same question: at which positions does the needle appear in the haystack?

It sounds trivial because your eyes do it so easily. But a computer has no eyes. It can only compare one character with another, one pair at a time. The whole art of string matching is about how few of those comparisons you can get away with. Fewer comparisons mean a faster search, and when the haystack holds a hundred million characters, the difference between a clever method and a careless one is the difference between a blink and a coffee break.

The obvious method, and why it is not enough

Imagine you write the needle on a strip of tracing paper and lay it over the start of the haystack. If every letter lines up, you have a match. If any letter disagrees, you slide the strip one place to the right and start checking again from the strip’s first letter. This is the naive or brute-force method, and it is the one most people invent on their own.

For ordinary text it is fine. Searching for “budget” in an essay, most positions fail on the very first letter, so each slide costs one comparison. The trouble starts when the text is repetitive. Suppose the haystack is a thousand letter A’s followed by a B, and the needle is fifty A’s followed by a B. At every starting position the first fifty letters match, and only the last comparison fails. The method then slides by one and repeats almost all the same work.

Look at the picture. The first attempt matched five letters, ABABA, and then failed at the sixth. A naive search forgets everything and starts again one step to the right. But we are not ignorant: we just saw that the text contains ABABA at that spot. The last three of those letters, ABA, are also the first three letters of the needle. So the needle can slide two places and carry on from its fourth letter, without re-checking ABA at all. That one observation is the whole of KMP.

Before we get there, let me put numbers on the pain. I wrote the naive search with a counter on every character comparison, and ran it on three kinds of text:

import random
from kmp import kmp_search

def naive_search(text, pat):
    hits, comps = [], 0
    for s in range(len(text) - len(pat) + 1):
        j = 0
        while j < len(pat):
            comps += 1
            if text[s + j] != pat[j]:
                break
            j += 1
        if j == len(pat):
            hits.append(s)
    return hits, comps

def horspool_search(text, pat):
    m = len(pat)
    shift = {c: m - 1 - i for i, c in enumerate(pat[:-1])}   # bad-character table
    hits, comps, s = [], 0, 0
    while s <= len(text) - m:
        j = m - 1
        while j >= 0:                    # compare from the END of the pattern
            comps += 1
            if text[s + j] != pat[j]:
                break
            j -= 1
        if j < 0:
            hits.append(s)
        s += shift.get(text[s + m - 1], m)
    return hits, comps

if __name__ == "__main__":
    essay = ("every time you press the find shortcut the page has to look through thousands of "
             "characters for a short phrase. a careless method restarts at every position, while "
             "a smarter one remembers what it has already seen and skips ahead. looking for a needle "
             "in a haystack sounds slow, yet careful programs do it in the blink of an eye. ") * 3
    random.seed(7)
    dna = "".join(random.choice("ACGT") for _ in range(100000))
    cases = [
        ("Repeated A, then B", "A" * 1000 + "B", "A" * 50 + "B"),
        ("English paragraph",  essay, "blink of an eye"),
        ("Random DNA",         dna,   "GATTACAGATTACA"),
    ]
    print(f"{'case':<20}{'text':>8}{'pat':>5}{'hits':>6}{'naive':>10}{'KMP':>9}{'Horspool':>10}")
    for name, text, pat in cases:
        a, ca = naive_search(text, pat)
        b, cb = kmp_search(text, pat)
        c, cc = horspool_search(text, pat)
        assert a == b == c
        print(f"{name:<20}{len(text):>8}{len(pat):>5}{len(a):>6}{ca:>10}{cb:>9}{cc:>10}")

Output:

case                    text  pat  hits     naive      KMP  Horspool
Repeated A, then B      1001   51     1     48501     1951      1001
English paragraph        987   15     3      1018      990       163
Random DNA            100000   14     0    133365   124971     47163

On the repeated-A text the naive method needed 48,501 comparisons to scan a text only 1,001 characters long, roughly 48 for every character. The same job took KMP 1,951 and the Horspool method (more on that shortly) 1,001. On a plain English paragraph the three were all close, because ordinary text rarely has long near-misses. This matters: the naive method is not slow on average. It is slow on the wrong input, and a program that handles user-supplied text cannot choose its input.

In the worst case the naive method needs about n × m comparisons, where n is the haystack length and m the needle length. A 100,000-character log and a 1,000-character needle could mean a hundred million comparisons. KMP needs about n + m.

The big idea: never throw away what you learned

Here is a human version of the idea. You are reading a phone book looking for the name “ANANAS”. You read A, N, A, N, A, and then the next letter is not S, it is N. A naive reader would go back to the second letter of the page and start over. But you already know that the last few letters you read were A, N, A, and that is exactly how ANANAS begins. So you just carry on as if you had started a short while ago, already three letters into the name.

KMP formalises that gut feeling. Before it touches the haystack, it studies the needle alone and prepares a small cheat sheet: for each position in the needle, how much of the needle’s own beginning is also its ending? That cheat sheet is the failure table, also called the prefix function or LPS table, short for “longest proper prefix which is also a suffix”.

Prefixes, suffixes and borders

These words sound heavy but the idea is plain. A prefix is the beginning of a word: for ABABA the prefixes are A, AB, ABA and ABAB. A suffix is the ending: A, BA, ABA and BABA. A border is something that is both. In ABABA, the string ABA is a prefix and also a suffix, so ABA is a border of length 3. (We exclude the whole word, which is why the table says “proper”.)

Why does a border matter? Because it tells you what the needle can safely fall back to after a failure. If you have matched ABABA and then hit a mismatch, you know the last three letters of what you matched are ABA, which is the start of the needle. So you resume as though you had matched only ABA. No searching backward in the haystack is needed.

Reading a failure table

The table holds one number per letter of the needle: the border length of the needle up to and including that letter. I printed the tables for three needles:

def build_lps(pat):
    """lps[i] = length of the longest proper prefix of pat[:i+1]
    that is also a suffix of it."""
    lps = [0] * len(pat)
    k = 0                                # length of the prefix matched so far
    for i in range(1, len(pat)):
        while k > 0 and pat[i] != pat[k]:
            k = lps[k - 1]               # fall back to a shorter prefix
        if pat[i] == pat[k]:
            k += 1
        lps[i] = k
    return lps


def kmp_search(text, pat):
    """Return (list of match positions, number of character comparisons)."""
    lps = build_lps(pat)
    hits, comps, k = [], 0, 0
    for i, ch in enumerate(text):        # the text pointer only moves forward
        while True:
            comps += 1
            if ch == pat[k]:
                k += 1
                break
            if k == 0:
                break
            k = lps[k - 1]               # reuse what we already matched
        if k == len(pat):
            hits.append(i - k + 1)
            k = lps[k - 1]               # allow overlapping matches
    return hits, comps


if __name__ == "__main__":
    for pat in ("ABABAC", "ABCDABD", "AAAB"):
        lps = build_lps(pat)
        print(f"pattern {pat}")
        print("  char:", " ".join(pat))
        print("  lps :", " ".join(map(str, lps)))
    print()
    hits, comps = kmp_search("ABABABAC", "ABABAC")
    print("search ABABAC in ABABABAC -> start", hits, "after", comps, "comparisons")

Output:

pattern ABABAC
  char: A B A B A C
  lps : 0 0 1 2 3 0
pattern ABCDABD
  char: A B C D A B D
  lps : 0 0 0 0 1 2 0
pattern AAAB
  char: A A A B
  lps : 0 1 2 0

search ABABAC in ABABABAC -> start [2] after 9 comparisons

For ABABAC the table reads 0, 0, 1, 2, 3, 0. Read it this way: after matching the first five letters ABABA, the border is 3, so if the sixth letter fails, fall back to having matched 3 letters. The final C has no border, hence 0. For ABCDABD the table shows 1 and 2 under the second A and B, because the needle starts again with AB halfway through. For AAAB the table climbs 0, 1, 2 because every A is a continuation of the same run; this is precisely the shape of needle that wrecks the naive method, and also precisely where KMP shines.

Notice the first entry is always 0, since a single letter has no proper prefix. A needle with no repeated structure, such as ABCDEF, gets all zeros, and then KMP behaves almost like the naive method, because there is nothing to reuse.

The search itself, step by step

With the table ready, the search runs two pointers. One walks through the haystack and only ever moves forward. The other, call it k, counts how many letters of the needle are currently matched. At each haystack letter you do one of three things:

• It matches the next needle letter. Increase k by one. If k now equals the needle length, you found a match.
• It does not match and k is above zero. Fall back: set k to the table entry just before it, then try the same haystack letter again against the shorter match.
• It does not match and k is zero. Nothing to fall back to. Move to the next haystack letter.

Here is the whole algorithm, which is shorter than most people expect:

def kmp_search(text, pat):
    """Return (list of match positions, number of character comparisons)."""
    lps = build_lps(pat)
    hits, comps, k = [], 0, 0
    for i, ch in enumerate(text):        # the text pointer only moves forward
        while True:
            comps += 1
            if ch == pat[k]:
                k += 1
                break
            if k == 0:
                break
            k = lps[k - 1]               # reuse what we already matched
        if k == len(pat):
            hits.append(i - k + 1)
            k = lps[k - 1]               # allow overlapping matches
    return hits, comps

Trace the earlier example. The haystack is ABABABAC and the needle ABABAC. The first five letters match, so k climbs to 5. The sixth haystack letter is B but the needle wants C, a mismatch. The table entry for the fifth needle letter is 3, so k drops to 3, meaning “ABA is still matched”. The needle’s fourth letter is B, which matches the haystack’s B, so k rises to 4. Then A matches, k is 5, then C matches, k is 6, and 6 equals the needle length: a match starting at position 2. The program output said exactly that, found at start 2 after 9 comparisons, for a haystack of 8 letters.

Why it is fast: the counting argument

The inner loop looks scary because of the fallback, which could in theory repeat many times. Here is why it cannot get out of hand. Each time the haystack pointer advances, k can grow by at most one. Each fallback strictly lowers k. So the total number of fallbacks over the whole search can never exceed the total number of increases, and that is at most n. Add the n forward steps and the fallbacks and you get at most about 2n comparisons. Building the table works the same way and costs about m. The total, n plus m, is called linear time, and it holds for any input.

That is why the experiment gave 1,951 comparisons for the 1,001-character repeated text. It lands just under the theoretical ceiling of 2n, which is 2,002. The algorithm is nearly as slow as it is allowed to be on that input, and still about twenty-five times better than the naive method.

Is KMP always the fastest? Honestly, no

This is the part most tutorials skip. Look again at the third row of the comparison output. On 100,000 random letters of DNA, using a 14-letter needle, KMP made 124,971 comparisons against naive’s 133,365. That is barely better. And the Horspool method, a cousin I have not explained yet, needed only 47,163. KMP’s selling point is the guarantee: it never degrades. It does not promise to win on friendly input.

Why did Horspool win so clearly on ordinary text? Because it uses the opposite trick. Instead of comparing the needle from the front, it compares from the back. If the haystack letter lined up with the needle’s last position is a letter that does not appear in the needle at all, say a Z when searching for “needle”, then no placement overlapping that Z can possibly match, and the whole needle can jump forward by its full length in one step. On English text with a 15-letter needle, that means looking at only about one letter in every several. The English row shows it: 163 comparisons for a 987-character text.

The family of methods built on this backward comparison is called Boyer-Moore, and Horspool is its simplified cousin. Well-known command line tools such as GNU grep are widely documented as using skip-ahead ideas of this kind for plain-text patterns, which is a large part of why searching a gigabyte of logs takes seconds. The longer your needle, the more you can skip, which feels backward until you think about it: more letters to check also means more chances to rule out a placement early.

What Ctrl+F is actually doing

I want to be careful here. Browsers and editors do not publish the exact algorithm they use, it varies between programs and versions, and I would not want to state one as fact. What I can describe with confidence is the shape of the job, because it is the same everywhere:

• Normalise. Most find boxes ignore case by default, so the program compares in a lowercase form, and often ignores accents too.
• Scan. It walks through the visible text of the page, using some string matching routine like the ones in this article.
• Collect every hit. Not just the first. Each match position is stored so the program can count them and jump between them.
• Highlight and report. It paints the matches, shows “3 of 17”, and scrolls to the one you are on.

And here is the honest truth about the word “instantly”. A typical page holds maybe fifty thousand characters. Even the naive method on ordinary text does that in a tiny fraction of a second on a modern machine. My own measurement scanned 300,000 characters in about 35 milliseconds with the slowest method, and I wrote that one in Python, which is itself slow. The instant feel comes mostly from raw hardware speed and the fact that ordinary text is friendly. The cleverness of KMP matters when the text is huge, repetitive, or arrives from an untrusted source and you cannot risk a pathological case.

Counting matches is trickier than it looks

One subtle thing your find box must decide: do matches overlap? Search for “aa” in “aaaaa”. Do you report two hits (positions 0 and 2, taking turns) or four (positions 0, 1, 2 and 3)? Different tools answer differently, and the choice matters when you display a count. I tested three common approaches:

import re
from kmp import kmp_search

text, pat = "aaaaa", "aa"
print("str.count      :", text.count(pat), "(non-overlapping)")
print("re.findall     :", len(re.findall(pat, text)), "(non-overlapping)")
print("KMP, all hits  :", len(kmp_search(text, pat)[0]), "at", kmp_search(text, pat)[0])

doc = "The cat sat. The Cat ran. A cat, the CAT."
print()
print("exact 'cat'    :", doc.count("cat"))
print("ignore case    :", doc.lower().count("cat"))
print("whole word     :", len(re.findall(r"\bcat\b", doc, re.I)))

Output:

str.count      : 2 (non-overlapping)
re.findall     : 2 (non-overlapping)
KMP, all hits  : 4 at [0, 1, 2, 3]

exact 'cat'    : 2
ignore case    : 4
whole word     : 4

Python’s count and the regular expression finder both say 2, because they skip past each match before looking again. KMP, as I wrote it, resets to the border after a match and finds all 4 overlapping hits. Neither is wrong; they answer different questions. The second block shows the other classic gotcha: exact search for “cat” finds 2 hits in my sentence, while ignoring case finds 4. If a user types a word and sees “2 results” when they can plainly see four, that is a case-sensitivity bug, not an algorithm bug.

The race: real timings

I timed four methods on two inputs: ordinary text, and the worst case for the naive method. These are pure Python implementations, so absolute numbers are modest, but the shape is what counts.

import random, time
from kmp import kmp_search
from compare import naive_search, horspool_search

def best(fn, *a, runs=3):
    t = 1e9
    for _ in range(runs):
        s = time.perf_counter(); fn(*a); t = min(t, time.perf_counter() - s)
    return t * 1000

random.seed(1)
text = "".join(random.choice("abcdefghijklmnopqrstuvwxyz ") for _ in range(300000))
pat = "zzqxjvkw"
print("Ordinary text, 300,000 characters, 8-letter pattern (milliseconds)")
for name, fn in (("naive", naive_search), ("KMP", kmp_search), ("Horspool", horspool_search)):
    print(f"  {name:<10}{best(fn, text, pat):>9.1f}")
print(f"  {'str.find':<10}{best(lambda t, p: t.find(p), text, pat):>9.1f}")

bad = "a" * 60000 + "b"
badpat = "a" * 150 + "b" + "c"
print()
print("Worst case for naive, 60,000 letters (milliseconds)")
print(f"  {'naive':<10}{best(naive_search, bad, badpat, runs=1):>9.1f}")
print(f"  {'KMP':<10}{best(kmp_search, bad, badpat):>9.1f}")
print(f"  {'str.find':<10}{best(lambda t, p: t.find(p), bad, badpat):>9.1f}")

Output (your numbers will differ a little from run to run):

Ordinary text, 300,000 characters, 8-letter pattern (milliseconds)
  naive          36.9
  KMP            27.8
  Horspool        8.5
  str.find        0.2

Worst case for naive, 60,000 letters (milliseconds)
  naive         709.9
  KMP             7.8
  str.find        0.1

Two lessons jump out. First, on ordinary text the order was Horspool, then KMP, then naive, all within a factor of five. The built-in str.find beat all of them by a huge margin, because it is written in C, and recent versions of Python combine several strategies inside it, including a method called Two-Way for longer needles. In real programs, use the built-in. Writing KMP yourself is for learning, for languages without a good built-in, or for streaming problems where you cannot hold the whole text.

Second, on the nasty input the naive search took several hundred milliseconds while KMP took under ten, roughly ninety times faster on my run, and the gap grows as the text grows. That is the scenario that justifies the algorithm: it turns a catastrophic input into an ordinary one.

Other string matching ideas worth knowing

Rabin-Karp: compare fingerprints

Instead of comparing letters, compute a numeric fingerprint, a hash, of the needle, and a rolling hash of each window of the haystack. Sliding the window one step updates the hash in constant time. Only when two fingerprints agree do you check the actual letters. The method is commonly described as a building block in plagiarism detection, because it extends naturally to checking many fragments at once.

Aho-Corasick: many needles at once

What if you have ten thousand needles, such as a database of virus signatures or a list of banned words? Running KMP ten thousand times is wasteful. Aho-Corasick builds one automaton from all the needles, a generalisation of the KMP failure table, and scans the haystack once. Antivirus engines such as ClamAV are known to use it.

Suffix structures: search many times

If the haystack is fixed and you will search it again and again, as genome databases do, you can pay once to build an index such as a suffix array, and then each query takes time depending mostly on the needle rather than the haystack. Scanning three billion DNA letters for every query would be hopeless.

Where string matching shows up in daily life

You use these algorithms far more often than you press Ctrl+F. Click through five everyday situations and notice how the needs differ: sometimes you want every match, sometimes only a guarantee, sometimes thousands of needles at once.

Which method should you reach for?

When someone asks me which algorithm to use, I answer with a short sequence of questions. In practice the first question ends the conversation nine times out of ten.

Common mistakes and how to avoid them

• Reimplementing what the language already does well. Python’s find, JavaScript’s indexOf and Java’s indexOf are tuned and tested. Write KMP when you need streaming, custom matching or a guaranteed bound.
• Forgetting overlapping matches. Decide up front whether “aa” in “aaaaa” counts as two hits or four.
• Ignoring case and accents. Normalise both strings the same way before searching, or users will report missing results.
• Treating text as plain letters when it is not. In Unicode, an accented é can be one character or an e followed by a combining accent. Normalise the text, or two identical-looking strings will not match.
• Off-by-one errors in the failure table. The fallback is lps[k - 1], not lps[k]. This is the most common bug in hand-written KMP.
• Forgetting the empty needle. Decide what searching for an empty string means and handle it before you build a table.
• Passing user input to a regular expression. Characters such as a dot or a bracket have special meaning. Use re.escape or a plain string search.
• Searching inside a loop over a huge list. One search is cheap. Ten thousand searches over a megabyte each is not. Build an index or use a multi-pattern method.

A mental model that sticks

Think of reading a street name on a long road sign while driving past. The naive method is a driver who, on spotting one wrong letter, stops, reverses to the beginning of the sign, and starts reading again. KMP is a driver who has memorised the sign’s own pattern of repeats and never reverses: after a wrong letter he glances at his memory and says, “fine, I have already read the last three letters of the right word”, and keeps driving. Horspool is a driver who reads from the far end of the sign first, and when that letter is not in the word at all, leaps ahead by the whole sign’s length.

Practice problems with answers

Try each one on paper before you tap to check.

1. Build the failure table for ABAB.

0 0 1 2. The border of ABA is A (length 1) and the border of ABAB is AB (length 2).

2. Build the failure table for AABAAB.

0 1 0 1 2 3. The word repeats itself, so the border keeps growing: AABAA ends with AA, and AABAAB ends with AAB.

3. Build the failure table for ABCABD.

0 0 0 1 2 0. AB repeats, giving 1 and 2, but the final D breaks the pattern and drops back to 0.

4. How many overlapping matches of aa are there in aaaaa?

4, starting at positions 0, 1, 2 and 3. A non-overlapping count gives only 2.

5. Searching AAB in AAAAAB: how many comparisons do the three methods need?

From my run: naive 12 (three at each of four starting positions), KMP 9 and Horspool 6. All three find the single match at position 3.

6. Why does the failure table for ABCDEF give no help?

Every entry is 0. The word has no border anywhere, so after a mismatch there is nothing to reuse and KMP behaves almost like the naive method.

7. The haystack has 1,000,000 letters. About how many comparisons can KMP need at most?

About 2,000,000, plus a tiny amount to build the table. The naive method could need up to a thousand times more if the needle were 1,000 letters long.

Test yourself: five quick questions

Tap a question to reveal the answer. The correct option is marked.

What does the KMP failure table store for each position of the needle?

1. The number of times the letter appears
2. The position of the last mismatch
3. The length of the longest proper prefix that is also a suffix
4. The hash of the letters so far

It stores the border length, which says how much of the match can be reused after a mismatch.

Why does KMP never move its haystack pointer backward?

1. Because the failure table tells it how much is already matched
2. Because it skips every second letter
3. Because it sorts the text first
4. Because it reads the text twice

After a mismatch it only changes the needle position k, using what it already learned.

Which input is worst for the naive method?

1. Random letters
2. A very short needle
3. A text with no matches at all
4. Long runs of the same letter, with a needle that almost matches

Near-misses force it to repeat almost the same comparisons at every start position.

How does Horspool skip ahead?

1. It sorts the needle
2. It compares from the end and jumps when the last letter is not in the needle
3. It uses a hash of each window
4. It reads only vowels

If the letter under the needle’s last position cannot appear in a match, the whole needle can jump forward.

In ordinary Python code, what should you usually use to find a substring?

1. A hand-written KMP
2. The built-in find or the in operator
3. A nested loop
4. A regular expression for every case

The built-in is written in C and tuned. In my tests it took 0.2 ms where my Python KMP took 27.8 ms.

Frequently asked questions

What is the KMP algorithm?

Knuth-Morris-Pratt is a string matching algorithm that finds a pattern in a text in linear time. It builds a failure table from the pattern so that, after a mismatch, it never has to move backward in the text.

What is the time complexity of KMP?

O(n + m), where n is the text length and m the pattern length. Building the table costs about m steps and the search at most about 2n comparisons.

Is KMP what Ctrl+F uses?

Browsers and editors do not publish their exact method and it varies between programs, so I cannot say. All of them solve the same problem: normalise the text, scan for the pattern, collect every match and highlight it.

Why is the naive method sometimes good enough?

On ordinary text most positions fail on the first letter, so each slide costs about one comparison. It only becomes slow on repetitive or adversarial input, which is when guarantees matter.

What is the difference between KMP and Boyer-Moore?

KMP compares from the front and uses a failure table to avoid re-checking letters. Boyer-Moore compares from the end and skips ahead using the letters it sees, which is often much faster on plain text but lacks KMP’s simple worst-case guarantee in its simplified forms.

Should I implement string search myself?

Rarely. Use your language’s built-in search for everyday work. Implement KMP to learn, for streaming input, or when you need a guaranteed bound on a pattern you control.