Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 225 ยท Strings

Pattern Matching: Naive and KMP

Search for a pattern in a text. Start with brute force O(nm), then learn the KMP failure table (LPS) and see step-by-step traces and comparison counts.

Pattern matching (also called substring search) asks: where does the string pattern occur inside the longer string text? It is what Ctrl+F, grep, DNA search and plagiarism checkers do all day. Python gives you text.find(pattern) and pattern in text, but to understand why a clever algorithm is fast, we implement the search ourselves.

Let n = len(text) and m = len(pattern). The naive algorithm tries every alignment and takes O(n*m) in the worst case. The Knuth-Morris-Pratt (KMP) algorithm never moves backwards in the text and takes O(n + m). The secret is a small table built from the pattern alone that tells KMP how much of its previous work it can keep after a mismatch.

You will see this lesson's ideas again in the Z-algorithm, Rabin-Karp and string DP. It helps to know the cost of string operations from Strings in DSA first.

The naive algorithm

Slide the pattern along the text one position at a time. At each alignment i, compare the pattern with text[i:i+m] character by character, stopping at the first mismatch. If all m characters match, record i.

TEXT
text:    A B A B C A B A B D
pattern: A B A B D

i=0: A B A B C      compare 5 chars, mismatch at the last (C vs D)
       A B A B D
i=1:   B != A        mismatch at once
i=2:     A B A B D   ...
Python Naive search with a comparison counter

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

On ordinary text, mismatches happen almost immediately, so the naive method is close to O(n). The bad case is repetitive data. Searching "AAAAAAAAAA" for "AAAB" compares almost the whole pattern at each of the 7 alignments (4 comparisons each, 28 in all, as the output shows). In general, a text of n letters A and a pattern of m - 1 letters A followed by a B costs about (n - m + 1) * m comparisons: O(n*m).

Time Extra space
Naive O(n*m) worst case, about O(n) typical O(1)
KMP O(n + m) always O(m)

The waste in the naive algorithm

Look at the failure above. After matching ABAB and failing on the last character, the naive algorithm moves to i + 1 and throws away what it learned. But we know the last four text characters are ABAB. The next alignment that could possibly match must start where the text suffix AB is also a prefix of the pattern, so we can restart comparing at pattern position 2 instead of 0, without re-reading the text.

KMP formalizes this: after a mismatch, the pattern slides forward to the longest position that is still consistent with what we have read, and the text pointer never goes back.

The failure table (LPS)

For each prefix of the pattern, store the length of its longest proper prefix that is also a suffix (LPS). "Proper" means not the whole string. Call the table lps: lps[i] is the LPS of pattern[0..i].

TEXT
pattern:  A  B  A  B  D
index:    0  1  2  3  4
lps:      0  0  1  2  0

lps[3] = 2   because "ABAB" has prefix "AB" equal to suffix "AB"
lps[4] = 0   because "ABABD" ends in D, which starts no prefix

A bigger example, "AABAAAB":

TEXT
pattern:  A  A  B  A  A  A  B
lps:      0  1  0  1  2  2  3

Building the table is itself a mini KMP: match the pattern against itself. Keep k, the length of the current border. For each new character: while it does not match pattern[k] and k > 0, fall back with k = lps[k - 1]; if it matches, k += 1; store k.

Python Build the LPS table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Although there is a while inside the for, the table is built in O(m): k increases by at most 1 per iteration and every fallback decreases it, so the total number of fallbacks cannot exceed the total number of increases. (This is an amortized argument, like in Amortized Analysis.)

Scan the text with index i and keep j, the number of pattern characters currently matched.

  1. If text[i] == pattern[j], advance both i and j.
  2. If j == m, a full match ends at i. Record the start i - m, then set j = lps[j - 1] to look for overlapping matches.
  3. On a mismatch: if j > 0, set j = lps[j - 1] without moving i; otherwise advance i.
Python KMP search with a trace

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the trace carefully. At i = 4 the text has C but the pattern expects D after ABAB (j = 4). The table says lps[3] = 2, so KMP sets j = 2: it keeps AB as matched and compares C with pattern[2] = A. That also fails, falls back to j = 0, and finally the scan moves on. The text index i never decreases.

TEXT
text:     A B A B C A B A B D
pattern:  A B A B D                 fail at C (j=4)
                A B A B D           pattern slides: only "AB" is reused
                      A B A B D     found at index 5

Why it is O(n + m)

Each loop iteration either increases i or decreases j (via the table). j can only go up when i goes up, and it never drops below 0, so the number of decreases is at most the number of increases, which is at most n. The loop therefore runs fewer than 2n times, plus O(m) to build the table.

Counting comparisons: naive versus KMP

Let us put both algorithms on the same bad input and a normal input and count character comparisons.

Python Comparison counts on bad and normal inputs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

On the repetitive input, the naive count is on the order of n * m while KMP stays below 2n. On the English sentence, the two are close, which is why plain find is fine for most text. KMP is worth its extra code when patterns or texts are highly repetitive (DNA, logs), or when you need a guaranteed worst case, or when the text arrives as a stream: KMP never looks back, so it can process one character at a time.

Finding all occurrences and useful variations

KMP naturally reports overlapping matches ("AAA" in "AAAAA" occurs at 0, 1 and 2). Some quick applications of the LPS table alone:

  • Repeated substring: a string of length L is built from a repeated block if L % (L - lps[-1]) == 0 and lps[-1] > 0.
  • Shortest palindrome by adding in front: compute the LPS of s + "#" + reverse(s).
  • Prefix function is the official name for the LPS array; the Z-algorithm computes a cousin of it.
Python Overlapping matches and repeated-block detection

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Concatenating pattern + sentinel + text lets one prefix-function pass do the whole search: any position where the value equals m marks a match that ends there. The sentinel character guarantees no border can cross the boundary.

Common mistakes

  • Moving i back after a mismatch. That reverts KMP to the naive algorithm.
  • Using lps[j] instead of lps[j - 1]. The table entry before the failing position is the one you need.
  • Skipping the fallback loop while building the table (using if instead of while), which gives wrong tables for patterns like "AABAAAB".
  • Forgetting overlap after a full match: set j = lps[m - 1], not 0, unless you want non-overlapping matches only.
  • Empty pattern. Decide what it means (Python's "abc".find("") is 0) and guard against pattern[0] errors.
  • Thinking KMP is always faster in Python. The built-in find is written in C and tuned. KMP wins in operation counts and in guarantees, not in Python wall-clock time on small texts.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the worst-case time complexity of the naive substring search for a text of length n and a pattern of length m?

    There are about n alignments, and an adversarial input such as 'AAAA...' against 'AAAB' compares nearly all m characters at each.
  2. 2. What does lps[i] store?

    lps is the prefix function, also called the failure table. It tells KMP how many characters stay matched after a mismatch.
  3. 3. What is lps for the pattern ABABD?

    'ABA' has border 'A' (length 1) and 'ABAB' has border 'AB' (length 2). 'ABABD' has none, so its entry is 0.
  4. 4. On a mismatch with j > 0, what does KMP do?

    The text pointer never moves backwards. The pattern pointer falls back to the longest border that still agrees with the text already read.
  5. 5. Why is the KMP search O(n + m) even though j can fall back several times?

    Every iteration increases i or decreases j. Since j never goes below zero and only rises together with i, the loop runs fewer than 2n times.

Summary

  • Substring search finds where pattern (length m) occurs in text (length n).
  • The naive algorithm tries every alignment: O(n*m) worst case, usually fast on random text, bad on repetitive text.
  • KMP precomputes the LPS (prefix function) table from the pattern in O(m): the longest proper prefix that is also a suffix for each prefix.
  • On a mismatch KMP sets j = lps[j - 1] and never moves the text index backwards, giving O(n + m) time and O(m) space.
  • After a full match, j = lps[m - 1] finds overlapping matches.
  • The prefix function also answers period, repeated-block and shortest-palindrome questions.

Next: Rabin-Karp and String Hashing, a different way to search: compare numbers instead of characters.