The KMP Algorithm in Python: String Search Without Ever Going Backwards

Searching a text for a substring looks like it should be free. Line the pattern up at the start, compare characters until one disagrees, slide one place right, try again. Python spells it "needle" in haystack and you never think about it.

The obvious implementation has a failure mode that is easy to trigger. Looking for aaaaab inside ten a characters followed by a b — an eleven character text — costs 36 character comparisons. Scale both sides up and the cost is the product of the two lengths, not the sum.

The waste has a precise shape. Every time an alignment fails, the naive search slides the pattern one place right and starts from scratch, even though it just read five characters that matched and is about to read four of them again. It learned something and threw it away. Knuth-Morris-Pratt, published in 1977 by Donald Knuth, James Morris and Vaughan Pratt, keeps it: one small table computed from the pattern alone, and with it the pointer into the text never moves backwards, not once, on any input. The search costs O(n + m), the text length plus the pattern length, with no bad case hiding behind the average.

The idea

The naive version, and where it wastes work

Start with the version you would write without thinking: at every possible starting position, compare the pattern character by character and give up at the first disagreement.

def naive_search(text: str, pattern: str) -> list[int]:
    """Return every start index where pattern occurs in text, by brute force.

    For each possible alignment of the pattern against the text, compare
    characters left to right and abandon the alignment at the first mismatch.
    """
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1))

    matches: list[int] = []
    for start in range(n - m + 1):
        offset = 0
        while offset < m and text[start + offset] == pattern[offset]:
            offset += 1
        if offset == m:
            matches.append(start)
    return matches


print(naive_search("ABABDABABABCABAB", "ABABCABAB"))
print(naive_search("aaaaaaaaaab", "aaaaab"))
print(naive_search("banana", "ana"))

[7]
[5]
[1, 3]

That is correct, including the overlapping matches of ana in banana at 1 and 3. The cost only bites when the pattern nearly matches in many places, so add a counter and measure.

def naive_search_counted(text: str, pattern: str) -> tuple[list[int], int]:
    """Brute force again, but also report how many characters it compared."""
    n, m = len(text), len(pattern)
    matches: list[int] = []
    comparisons = 0

    for start in range(n - m + 1):
        offset = 0
        while offset < m:
            comparisons += 1
            if text[start + offset] != pattern[offset]:
                break
            offset += 1
        if offset == m:
            matches.append(start)
    return matches, comparisons


for sample_text, sample_pattern in [
    ("ABABDABABABCABAB", "ABABCABAB"),
    ("aaaaaaaaaab", "aaaaab"),
]:
    found, count = naive_search_counted(sample_text, sample_pattern)
    print(f"{sample_pattern} in {sample_text}: {found}, {count} comparisons")

ABABCABAB in ABABDABABABCABAB: [7], 26 comparisons
aaaaab in aaaaaaaaaab: [5], 36 comparisons

Thirty-six comparisons to search eleven characters. There are n - m + 1 alignments and each can run the full length of the pattern before failing, so the worst case is (n - m + 1) * m comparisons: O(n × m). On a 1 MB text with a 1,000 character pattern of that shape, a billion comparisons.

Repetitive input is not exotic: DNA has a four-letter alphabet, log lines repeat the same prefixes, binary formats are full of zero bytes. And if an attacker picks the input, they can make this quadratic on purpose.

What a partial match already tells you

Here is the observation the whole algorithm rests on. Suppose you aligned the pattern at text position s, matched j characters, then hit a mismatch. You now know something exact and free: text[s : s + j] equals pattern[: j].

The naive version deletes that. But you can work out in advance, without looking at the text at all, which shifts are worth trying. A match beginning at s + k, for a shift k between 1 and j, needs its first j - k characters to line up with text[s + k : s + j] — which you already know, because those characters are pattern[k : j]. So the shift is worth trying only if

pattern[: j - k] equals pattern[k : j]

which says: some prefix of the pattern is also a suffix of pattern[: j]. A string that is both a proper prefix and a suffix of another string is called a border. "Proper" means not the whole string — otherwise everything borders itself and nothing ever shifts.

To shift as little as possible, so you never jump over a match, you want the longest border. The longest border of ABABCABAB is ABAB: those four characters open the pattern and also close it.

So after matching all nine characters, the next alignment to try is not one place right and not nine — it is five places right, because four characters are already verified. The longest border of every prefix of the pattern is the entire table KMP needs. It is called the failure function, or the LPS array, for longest proper prefix which is also a suffix.

Watching it work

Building the table for ABABCABAB

lps[index] is the length of the longest border of pattern[: index + 1]. Build it left to right carrying one variable, length, the border length of the previous prefix.

• Index 0, A. A one-character string has no proper prefix, so lps[0] = 0. Always.
• Index 1, B. length is 0, so try to extend the empty border: is pattern[1] equal to pattern[0]? B against A, no. lps[1] = 0.
• Index 2, A. length is 0. Is pattern[2] equal to pattern[0]? A against A, yes. length becomes 1, lps[2] = 1. The border of ABA is A.
• Index 3, B. length is 1. Is pattern[3] equal to pattern[1]? Yes. length becomes 2, lps[3] = 2. The border of ABAB is AB.
• Index 4, C. length is 2. Is pattern[4] equal to pattern[2]? C against A, no — AB cannot be extended. Fall back to the border of AB, which is lps[1] = 0, and try again: C against pattern[0], still no. Nothing is left, so lps[4] = 0. The C occurs nowhere else in the pattern, so it destroys every border.
• Index 5, A. length is 0 and A matches pattern[0], so lps[5] = 1.
• Index 6, B. Matches pattern[1]. lps[6] = 2.
• Index 7, A. Matches pattern[2]. lps[7] = 3.
• Index 8, B. Matches pattern[3]. lps[8] = 4 — the ABAB from the diagram above.

Index 4 is the step worth staring at. When a border cannot be extended, the next candidate is the border of that border. That is why the table can be built out of itself, and it is the same move the search makes on a mismatch.

Searching ABABDABABABCABAB

Now search the text ABABDABABABCABAB with i as the text pointer and j as the pattern pointer. j doubles as "how many characters currently match", so the pattern sits at text position i - j.

Alignment at 0. A, B, A, B match, so i and j both reach 4. Then text[4] is D and pattern[4] is C. Mismatch, four characters matched. Consult lps[3] = 2: two of them survive. Set j = 2 and leave i at 4. The pattern has slid right by two.

Alignment at 2. Compare text[4], still D, against pattern[2], A. Mismatch again with j = 2, so consult lps[1] = 0. Set j = 0, i unchanged.

Alignment at 4. With j at 0 there is nothing left to fall back on. D against A fails, and only now does i move, to 5.

Alignment at 5. A, B, A, B match again, taking i to 9 and j to 4. text[9] is A, pattern[4] is C. Mismatch, lps[3] = 2 again, j = 2, i stays at 9.

Alignment at 7. The payoff. Compare text[9] against pattern[2]: A against A, a match. The characters text[7:9] were never re-read, and the search rolls straight on to a full match starting at index 7.

Five alignments, 19 character comparisons, and the text pointer moved right 16 times and left zero times. Naive search needed 26 comparisons on the same input.

The code

Two functions. The table is the harder one.

def build_lps(pattern: str) -> list[int]:
    """Longest proper prefix that is also a suffix, for every prefix of pattern.

    lps[index] is the length of the longest string that is both a proper
    prefix and a suffix of pattern[:index + 1]. "Proper" means it is not the
    whole prefix, so the value is always at most index.
    """
    lps = [0] * len(pattern)
    length = 0  # length of the border of the prefix ending at index - 1

    for index in range(1, len(pattern)):
        # The border cannot be extended by pattern[index], so try the next
        # shortest border. lps[length - 1] is exactly that border's length.
        while length > 0 and pattern[index] != pattern[length]:
            length = lps[length - 1]

        if pattern[index] == pattern[length]:
            length += 1

        lps[index] = length

    return lps


demo_pattern = "ABABCABAB"
print(" ".join(demo_pattern))
print(" ".join(str(value) for value in build_lps(demo_pattern)))
print(build_lps("aaaaab"))
print(build_lps("abcdef"))

A B A B C A B A B
0 0 1 2 0 1 2 3 4
[0, 1, 2, 3, 4, 0]
[0, 0, 0, 0, 0, 0]

Those are the two extremes and one real case. A pattern of distinct characters has no borders, so every entry is 0 and KMP degenerates to naive search — which costs nothing, because naive search is already linear when nothing ever partially matches. A run of identical characters has the maximum possible borders, so the table counts up.

The search loop is short once the table exists.

def kmp_search(text: str, pattern: str) -> list[int]:
    """Every start index of pattern in text, found in O(len(text) + len(pattern)).

    The text index never decreases: a mismatch rewinds the pattern index to a
    shorter border instead of re-reading characters of the text.
    """
    if not pattern:
        return list(range(len(text) + 1))

    lps = build_lps(pattern)
    matches: list[int] = []
    text_index = 0
    pattern_index = 0

    while text_index < len(text):
        if text[text_index] == pattern[pattern_index]:
            text_index += 1
            pattern_index += 1
            if pattern_index == len(pattern):
                matches.append(text_index - pattern_index)
                # Overlapping matches count, so slide to the longest border
                # rather than starting the pattern from scratch.
                pattern_index = lps[pattern_index - 1]
        elif pattern_index > 0:
            pattern_index = lps[pattern_index - 1]  # text_index stays put
        else:
            text_index += 1

    return matches


print(kmp_search("ABABDABABABCABAB", "ABABCABAB"))
print(kmp_search("banana", "ana"))
print(kmp_search("aaaa", "aa"))
print(kmp_search("hello", "xyz"))

[7]
[1, 3]
[0, 1, 2]
[]

How the code maps to the idea

lps[length - 1] is the fallback, in both functions. If the current border has length length, its own longest border has length lps[length - 1]. Following that chain from a border to the border of the border enumerates every border of the current prefix, longest first — which is the complete list of shifts worth trying, in the order that shifts least.

The off-by-one is j - 1, not j. On a mismatch you have matched pattern[: j], a string of length j, whose table entry lives at index j - 1. Writing lps[pattern_index] is the most common KMP bug: it consults the border of a prefix one character longer than the one you actually matched, so the pattern shifts too far and real matches disappear.

The three branches cover every case. Characters agree: advance both pointers. Characters disagree with something matched: rewind j, hold i. Characters disagree with nothing matched: there is no partial match to salvage, so advance i. Note that i increases in two branches and decreases in none — the whole "never goes backwards" claim is visible in three lines.

After a full match, j becomes lps[m - 1] rather than 0. Resetting to 0 works for non-overlapping searches but misses aa at index 1 of aaaa. Using the border treats a completed match exactly like a mismatch one character past the end, which is what it is.

Edge cases fall out of the arithmetic. An empty text never enters the loop. A pattern longer than the text can never drive j to len(pattern). A pattern that never matches returns an empty list with no special casing. The one case needing a guard is the empty pattern, since pattern[0] raises IndexError; the early return matches Python's convention, where "abc".find("") is 0.

Here is every comparison the search makes, printed by the algorithm itself, so you can check the hand trace above line by line.

def kmp_trace(text: str, pattern: str) -> None:
    """Print one line per character comparison the search performs."""
    lps = build_lps(pattern)
    text_index = pattern_index = 0
    step = 0

    while text_index < len(text):
        step += 1
        i_before, j_before = text_index, pattern_index
        text_char, pattern_char = text[text_index], pattern[pattern_index]

        if text_char == pattern_char:
            text_index += 1
            pattern_index += 1
            action = "match"
            if pattern_index == len(pattern):
                action = f"MATCH at {text_index - pattern_index}"
                pattern_index = lps[pattern_index - 1]
        elif pattern_index > 0:
            action = f"mismatch: j = lps[{j_before - 1}] = {lps[j_before - 1]}"
            pattern_index = lps[j_before - 1]
        else:
            action = "mismatch: j is 0, so i moves"
            text_index += 1

        print(f"{step:>2}  i={i_before:>2} j={j_before}  {text_char} vs {pattern_char}  {action}")


kmp_trace("ABABDABABABCABAB", "ABABCABAB")

 1  i= 0 j=0  A vs A  match
 2  i= 1 j=1  B vs B  match
 3  i= 2 j=2  A vs A  match
 4  i= 3 j=3  B vs B  match
 5  i= 4 j=4  D vs C  mismatch: j = lps[3] = 2
 6  i= 4 j=2  D vs A  mismatch: j = lps[1] = 0
 7  i= 4 j=0  D vs A  mismatch: j is 0, so i moves
 8  i= 5 j=0  A vs A  match
 9  i= 6 j=1  B vs B  match
10  i= 7 j=2  A vs A  match
11  i= 8 j=3  B vs B  match
12  i= 9 j=4  A vs C  mismatch: j = lps[3] = 2
13  i= 9 j=2  A vs A  match
14  i=10 j=3  B vs B  match
15  i=11 j=4  C vs C  match
16  i=12 j=5  A vs A  match
17  i=13 j=6  B vs B  match
18  i=14 j=7  A vs A  match
19  i=15 j=8  B vs B  MATCH at 7

Read the i column downwards: 0, 1, 2, 3, 4, 4, 4, 5, 6, … It repeats, but it never goes down.

Complexity

A single loop iteration is not bounded — one mismatch can trigger a whole chain of fallbacks. The bound comes from an amortised argument: those fallbacks have to be paid for by earlier work.

Building the table costs at most 2m comparisons. Watch length. It increases by 1 at most once per value of index, so across the whole build it increases at most m - 1 times. Every iteration of the inner while loop strictly decreases it, and it never drops below 0. A quantity that goes up at most m - 1 times in total can come down at most m - 1 times in total. So the inner loop runs at most m - 1 times across the entire build, not per index, and the total comparison count stays under 2m. Preprocessing is O(m).

Searching costs at most 2n comparisons. The same argument one level up. pattern_index increases only in the branch where the characters agree, and that branch also increases text_index, so it goes up at most n times in total — and therefore comes down at most n times in total. Every loop iteration performs exactly one comparison and then either increases text_index or decreases pattern_index, so there are at most n + n iterations. The scan is O(n).

Together: O(n + m) for the best case, the average case and the worst case alike. There is no adversarial input. Measure it on the pathological shape from the opening, scaled up.

def kmp_search_counted(text: str, pattern: str) -> tuple[list[int], int, int]:
    """KMP that reports (matches, comparisons building lps, comparisons scanning)."""
    lps = [0] * len(pattern)
    length = 0
    build_comparisons = 0

    for index in range(1, len(pattern)):
        while length > 0 and pattern[index] != pattern[length]:
            build_comparisons += 1
            length = lps[length - 1]
        build_comparisons += 1
        if pattern[index] == pattern[length]:
            length += 1
        lps[index] = length

    matches: list[int] = []
    scan_comparisons = 0
    text_index = pattern_index = 0

    while text_index < len(text):
        scan_comparisons += 1
        if text[text_index] == pattern[pattern_index]:
            text_index += 1
            pattern_index += 1
            if pattern_index == len(pattern):
                matches.append(text_index - pattern_index)
                pattern_index = lps[pattern_index - 1]
        elif pattern_index > 0:
            pattern_index = lps[pattern_index - 1]
        else:
            text_index += 1

    return matches, build_comparisons, scan_comparisons


haystack = "a" * 5000 + "b"
needle = "a" * 100 + "b"
naive_matches, naive_count = naive_search_counted(haystack, needle)
kmp_matches, build_count, scan_count = kmp_search_counted(haystack, needle)

print(f"text {len(haystack)} chars, pattern {len(needle)} chars")
print(f"naive: {naive_count} comparisons, matches {naive_matches}")
print(f"kmp:   {build_count + scan_count} comparisons "
      f"({build_count} to build the table, {scan_count} to scan), matches {kmp_matches}")
print(f"kmp bound 2n + 2m = {2 * len(haystack) + 2 * len(needle)}")

text 5001 chars, pattern 101 chars
naive: 495001 comparisons, matches [4900]
kmp:   10100 comparisons (199 to build the table, 9901 to scan), matches [4900]
kmp bound 2n + 2m = 10204

Forty-nine times fewer comparisons, and the measured 10,100 sits just under the predicted ceiling of 10,204. Double the text and naive search doubles once per pattern character; KMP simply doubles.

Space is O(m): one integer per pattern character, and nothing else scales. The text is read, never copied.

Correctness deserves checking rather than trusting, so here is an exhaustive comparison against brute force and against Python's own str.find, over every text of up to 8 characters and every pattern of up to 3 characters from a two-letter alphabet. Small alphabets maximise partial matches, which is precisely where wrong border logic shows up.

from itertools import product

pairs = 0
for text_length in range(9):
    for text_letters in product("ab", repeat=text_length):
        sample = "".join(text_letters)
        for pattern_length in range(1, 4):
            for pattern_letters in product("ab", repeat=pattern_length):
                needle_text = "".join(pattern_letters)
                expected = naive_search(sample, needle_text)
                assert kmp_search(sample, needle_text) == expected
                first = expected[0] if expected else -1
                assert sample.find(needle_text) == first
                pairs += 1

print(f"{pairs} text/pattern pairs agree with brute force and with str.find")

7154 text/pattern pairs agree with brute force and with str.find

When to use it, and when not to

In application Python, reach for the built-in. pattern in text, text.find(pattern), text.count(pattern) and re.finditer are implemented in C and will beat a hand-written KMP loop by roughly two orders of magnitude, because the constant factor of a Python-level loop dwarfs any saving in comparisons. CPython already protects you from the quadratic blow-up too: its string search is a Boyer-Moore-Horspool style skip loop with a Bloom filter over the pattern's characters, and since Python 3.10 it switches to the Crochemore-Perrin "two-way" algorithm for long needles, which carries the same O(n + m) worst case guarantee. Not KMP, same protection.

KMP is not the fastest algorithm in practice either. It reads every character of the text at least once. Boyer-Moore-Horspool does not: it compares from the right of the pattern, and when the mismatching text character occurs nowhere in the pattern it jumps forward by the pattern's full length. On English prose with a 20 character pattern it touches roughly one character in ten. KMP cannot beat linear, so on ordinary text it loses. What KMP sells is the guarantee — Horspool's worst case is still O(n × m).

Write KMP when one of these is true:

• You cannot rewind the input. A socket, a pipe, or a multi-gigabyte file you refuse to buffer. Because the text pointer never goes backwards, KMP consumes each character exactly once on arrival, with O(m) state and no window at all.
• The input is adversarial or genuinely repetitive. Attacker-supplied patterns, DNA, run-length-ish binary formats.
• You need the failure function for something else. It generalises directly to Aho-Corasick for many patterns at once, and m - lps[m - 1] gives the smallest period of a string for free.
• Your language's built-in search is naive. Java's String.indexOf is a straightforward O(n × m) scan.

The streaming case is where KMP is genuinely the right tool rather than a teaching exercise:

from typing import Optional


class StreamMatcher:
    """Report matches while consuming a stream one character at a time.

    Only the pattern and two integers are kept, so a 4 GB log can be scanned
    with a few hundred bytes of state.
    """

    def __init__(self, pattern: str) -> None:
        if not pattern:
            raise ValueError("pattern must not be empty")
        self.pattern = pattern
        self.lps = build_lps(pattern)
        self.pattern_index = 0
        self.consumed = 0

    def feed(self, character: str) -> Optional[int]:
        """Return the start index of a match ending at this character, else None."""
        while self.pattern_index > 0 and character != self.pattern[self.pattern_index]:
            self.pattern_index = self.lps[self.pattern_index - 1]

        if character == self.pattern[self.pattern_index]:
            self.pattern_index += 1

        self.consumed += 1

        if self.pattern_index == len(self.pattern):
            self.pattern_index = self.lps[self.pattern_index - 1]
            return self.consumed - len(self.pattern)
        return None


matcher = StreamMatcher("ana")
hits = [start for start in (matcher.feed(char) for char in "bananana") if start is not None]
print(hits)

[1, 3, 5]

Three overlapping matches in bananana, found while holding nothing but the pattern and two integers.

Do not use KMP for approximate matching. The border logic assumes exact character equality; allow typos or wildcards and the argument collapses, so use edit distance. For many patterns at once, build an Aho-Corasick automaton rather than running KMP once per pattern. If you search the same text repeatedly, do not scan at all — index it once with a suffix array or an FM-index.

One more honest number: on the 16 character example above, KMP costs 9 comparisons to build the table plus 19 to scan, against naive search's 26. Preprocessing is not free, and on short texts it does not pay for itself. KMP wins when n is large relative to m, or when one table is reused across many texts.

Where it shows up in the real world

Intrusion detection. The failure function generalises from one pattern to a trie of thousands; the result is the Aho-Corasick automaton, and it is the default multi-pattern matcher in the Snort and Suricata intrusion detection engines. They test each packet against tens of thousands of attack signatures in a single pass over the payload, which is only possible because the automaton never re-reads a byte.

Small-alphabet sequence scanning. DNA has four letters, so partial matches are constant and naive search degrades badly — exactly the input shape KMP handles. It is a reasonable tool for scanning reads for a fixed motif such as a restriction site or a sequencing adapter. Note the limit: the large read aligners such as BWA and Bowtie do not use KMP, because they answer millions of queries against one fixed reference genome, and it pays to build a Burrows-Wheeler/FM index of that genome once instead of streaming it per query.

Period detection. For a pattern of length m, the value m - lps[m - 1] is its shortest period, and the string is that period repeated exactly when the period divides m. abcabcabc has a final LPS entry of 6, and 9 − 6 = 3 divides 9, so it is abc three times.

Mostly, though, it is a building block. Aho-Corasick, the Z-algorithm and the general theory of string periodicity all descend from the failure function. Learning KMP is how you get access to them.

Common mistakes

Using lps[j] instead of lps[j - 1]. The table is indexed by last-character position, so the entry for a matched prefix of length j lives at j - 1. Getting it wrong shifts too far and silently drops matches.

Advancing the text pointer on a mismatch when j is above 0. The mismatched text character has not been consumed yet — the whole point is to re-test it against the shorter alignment. Advancing past it skips matches starting inside the region you already read.

Resetting j to 0 after a full match. It looks harmless and breaks overlapping searches: aa in aaaa returns two matches instead of three. Use lps[m - 1].

Letting the whole prefix count as its own border. If lps[index] could equal index + 1, the fallback length = lps[length - 1] would never shrink and the build loop would spin forever. "Proper" is doing real work in the definition.

Rebuilding the table inside the loop. Scanning 10,000 files for one pattern should call build_lps once, outside the file loop. Calling kmp_search per file is still correct and still linear, but it throws away the thing preprocessing buys you.

Forgetting the empty pattern. pattern[0] raises IndexError on an empty string. Decide what an empty pattern means, then handle it explicitly.

Practice

1. Add a first_only: bool = False parameter to kmp_search that returns as soon as it finds one match, and confirm the comparison count drops on a text with many occurrences.
2. Count the overlapping occurrences of aa in a string of 1,000 a characters, and explain from the LPS table why the answer is 999.
3. Write smallest_period(text) using len(text) - lps[-1], and use it to decide whether a string is some shorter string repeated a whole number of times.
4. Decide whether one string is a rotation of another with a single KMP search: check the lengths agree, then search the first inside the second concatenated with itself.
5. Extend the matcher so that ? in the pattern matches any character, then explain why the LPS table can no longer be built the same way.

Summary

KMP replaces "slide by one and start over" with "slide by exactly as much as the pattern's own structure permits". The table that says how much is the longest border of every prefix, built in O(m) by the same fallback move the search uses. The result is a search whose text pointer only ever moves right, and a hard O(n + m) bound with no worst case to fear — but also an algorithm that reads every character, which is why skip-based searches beat it on ordinary prose and why Python's own str.find is built from different parts.

Keep reading

• Rabin-Karp — the other linear-average substring search, built from rolling hashes instead of borders.
• Big O Notation — the full treatment of the amortised argument used to prove the 2n bound.
• The Two Pointers Technique — the same "each pointer only moves one way" discipline, applied to arrays.
• Edit Distance — what to reach for when the match does not have to be exact.