String Matching — Algorithms Course

What you'll learn

Finding a pattern inside a text is one of computing's most common tasks — every "find" command runs it. The naive way is O(n·m); smarter algorithms — Rabin-Karp, KMP, and the Z-algorithm — reach linear time.

By the end you'll be able to:

Run the naive matcher and see its wasted work
Understand Rabin-Karp's rolling hash
Explain the KMP failure function and its linear time

The naive matcher

Try the pattern at every offset; at each, compare characters until a mismatch, then shift by one. It works, but it re-examines characters it has already seen — up to O(n·m). Watch it slide and compare:

Naive string matching

Naive search for ABAC

1/7Naive search: slide the pattern along the text, comparing left to right at each offset.

Align, compare left to right, and on a mismatch shift by just one — re-scanning characters.

Language

naive_search.py

def naive_search(text, pattern):
    n, m = len(text), len(pattern)
    for i in range(n - m + 1):       # every offset
        if text[i:i + m] == pattern: # compare the window
            return i
    return -1

Rabin-Karp

Rabin-Karp compares a hash of the pattern to the hash of each text window. The trick is a rolling hash: sliding the window one character updates the hash in O(1) (remove the leaving character, add the entering one) instead of rehashing from scratch. Matching hashes are then verified directly. Average O(n + m); great for multiple-pattern and plagiarism search.

Note

A hash collision means two different windows share a hash, so Rabin-Karp verifies each hash match character-by-character. With a good hash, collisions are rare and the average stays linear; the worst case is still O(n·m).

KMP & the failure function

Knuth-Morris-Pratt never re-scans the text. It precomputes a failure function (the lps array): for each pattern position, the length of the longest proper prefix that is also a suffix. On a mismatch, it slides the pattern by as much as that overlap allows — no backtracking in the text:

The KMP failure function for ABABC

lps[i] = length of the longest proper prefix of pattern[0..i] that is also a suffix.

KMP in code

Language

kmp.py

def build_lps(pattern):
    lps = [0] * len(pattern)
    k = 0
    for i in range(1, len(pattern)):
        while k > 0 and pattern[i] != pattern[k]:
            k = lps[k - 1]           # fall back
        if pattern[i] == pattern[k]:
            k += 1
        lps[i] = k
    return lps

def kmp_search(text, pattern):
    lps = build_lps(pattern)
    i = j = 0
    while i < len(text):
        if text[i] == pattern[j]:
            i += 1; j += 1
            if j == len(pattern):
                return i - j          # match!
        elif j > 0:
            j = lps[j - 1]            # jump, don't re-scan text
        else:
            i += 1
    return -1

Key idea

Building the lps array is O(m) and the scan is O(n), so KMP is O(n + m) in the worst case. The Z-algorithm achieves the same linear time with a slightly different precomputation (the Z-array of longest matches from each position).

Choosing a matcher

Algorithm	Preprocessing	Search	Note
`Naive`	None	O(n·m)	Simple, fine for short text
`Rabin-Karp`	O(m)	O(n + m) avg	Rolling hash; multi-pattern
`KMP`	O(m)	O(n + m)	No text backtracking
`Z-algorithm`	O(n + m)	O(n + m)	Z-array; versatile

Recap & quick check

Key takeaways

Naive matching is O(n·m) because it re-scans characters after a mismatch.
Rabin-Karp compares rolling hashes in O(1) per shift, verifying real matches — O(n+m) average.
KMP precomputes a failure function (lps) so it never backtracks in the text — O(n+m).
lps[i] is the longest proper prefix of the pattern's first i+1 chars that is also a suffix.
The Z-algorithm is another linear-time matcher via the Z-array.

Quick check

1. Why is naive string matching O(n·m)?

2. What makes Rabin-Karp efficient?

3. What does KMP's failure function (lps) store?

4. What is KMP's worst-case time complexity?

Single patterns are just the start. Next: structures for searching text at scale. Next up: Module 31 — Advanced String Algorithms.