String Matching

Why not brute force?

Naively sliding the pattern across the text and comparing is O(n*m). KMP (Knuth-Morris-Pratt) avoids re-checking characters it already matched by precomputing, for the pattern, how far to fall back on a mismatch — giving O(n + m).

KMP failure function

lps[i] stores the length of the longest proper prefix of pattern[0..i] that is also a suffix — this tells KMP how far to shift on a mismatch instead of restarting.

def build_lps(pattern):
    lps = [0] * len(pattern)
    length = 0
    i = 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length:
            length = lps[length - 1]
        else:
            lps[i] = 0
            i += 1
    return lps

def kmp_search(text, pattern):
    lps = build_lps(pattern)
    matches, i, j = [], 0, 0
    while i < len(text):
        if text[i] == pattern[j]:
            i, j = i + 1, j + 1
            if j == len(pattern):
                matches.append(i - j)
                j = lps[j - 1]
        elif j:
            j = lps[j - 1]
        else:
            i += 1
    return matches

Output:

kmp_search('ababcabab', 'abab')  # [0, 5]

Rabin-Karp at a glance

Rabin-Karp hashes the pattern and every window of the text, comparing hashes first (O(1) via a rolling hash) and only verifying character-by-character on a hash match. Great for searching many patterns at once.

Quick check

Test KMP's complexity.

Quick check: KMP's overall time complexity for searching pattern of length m in text of length n is:

• O(n*m)
• O(n + m)
• O(n log m)
• O(m^2)