AmouAI Hub/Courses/Data Structures & Algorithms/Chapter 28

Part 7 · Advanced and Applied · Chapter 28

String Algorithms

Find a needle in a haystack without re-reading the haystack. KMP never backs up, Rabin-Karp hashes a rolling window, and both are prettier than they look.

Reading

CLRS Ch. 32

Focus

Never re-read the text

Cost

O(n + m)

Needs

Arrays, hashing

By the end of this chapter you can

State the cost of naive matching and construct the input that makes it quadratic
Build KMP's failure function and explain what each entry means
Explain why KMP never moves the text pointer backwards
Implement a rolling hash and describe how Rabin-Karp handles collisions
Find palindromes by expanding around centres, and anagrams with a sliding count
Choose between the algorithms for a given matching problem

1The naive way, and why it is slow

Line the pattern up, compare left to right, slide one position on failure. Usually fine; occasionally catastrophic.

The obvious algorithm is two nested loops:

naive.py

def find_naive(text, pat):
    n, m = len(text), len(pat)
    for shift in range(n - m + 1):
        k = 0
        while k < m and text[shift + k] == pat[k]:
            k += 1
        if k == m:
            return shift
    return -1

On ordinary English text this is close to linear, because a mismatch usually happens on the first or second character. The worst case is another matter:

worst.pythe input that kills it

text = "A" * 100000 + "B"
pat  = "A" * 1000 + "B"

# Every one of the ~99,000 alignments matches 1000 characters and then fails
# on the last one. Roughly 10^8 comparisons to find a single occurrence.

The wasted work, named

Suppose the pattern is ABABC and you have matched ABAB before failing on the C. Naive matching now slides one position and re-compares from scratch — but you already know those four characters. They were ABAB.

And you know something about the pattern too: its prefix AB is also its suffix at that point. So instead of restarting, you can slide the pattern forward by two and continue from the middle of it, without re-reading a single character of the text.

That observation is the whole of KMP.

2KMP: never look back

Precompute, for every position in the pattern, how far you may safely jump on a mismatch. Then the text pointer only ever moves forward.

The precomputed table is the failure function (also called the prefix function or LPS array). Its definition is worth reading twice:

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

“Proper” means it may not be the whole thing, otherwise the answer is trivially i + 1 every time.

i	pat[0..i]	longest prefix = suffix	lps[i]
0	A	—	0
1	AB	—	0
2	ABA	A	1
3	ABAB	AB	2
4	ABABC	—	0
5	ABABCA	A	1
6	ABABCAB	AB	2
7	ABABCABA	ABA	3
8	ABABCABAB	ABAB	4

lps.pythe pattern matched against itself

def build_lps(pat):
    lps = [0] * len(pat)
    length = 0                       # length of the current prefix-suffix match
    i = 1
    while i < len(pat):
        if pat[i] == pat[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length:
            length = lps[length - 1]  # fall back — do NOT reset to 0
        else:
            lps[i] = 0
            i += 1
    return lps

The line everyone gets wrong

length = lps[length - 1] is the fallback, and writing length = 0 instead is the classic bug. It passes most test cases and fails on patterns with nested repeats.

Why it must be a fallback: if you were matching a prefix of length L and the next character disagrees, some shorter prefix-suffix may still be alive. lps[L-1] is exactly the next-longest candidate, so you drop to it and try again. It is the same recursive structure as the search itself — which is why building the table is literally KMP run on the pattern against itself.

kmp.pyO(n + m), guaranteed

def kmp_search(text, pat):
    """Index of the first occurrence, or -1."""
    if not pat:
        return 0
    lps = build_lps(pat)
    k = 0                                   # how much of pat currently matches
    for i, ch in enumerate(text):           # i NEVER goes backwards
        while k and ch != pat[k]:
            k = lps[k - 1]                  # slide the pattern, not the text
        if ch == pat[k]:
            k += 1
        if k == len(pat):
            return i - len(pat) + 1
    return -1

Why it is linear

The while loop looks like it could make the algorithm quadratic. It cannot, and the argument is a neat piece of amortised analysis.

k increases by at most 1 per character of text, so over the whole run it increases at most n times. Every iteration of the while loop strictly decreases k. A quantity that goes up at most n times in total cannot come down more than n times, so the inner loop runs O(n) times across the whole search — not per character.

Same shape of argument as the dynamic-array doubling in Chapter 3.

A phone number you keep re-dialling

You are dialling 0207-1234 and you misdial the last digit. Naive matching hangs up and starts from 0. KMP notices that what you have already dialled ends with a prefix of the number you want, and continues from there.

The failure function is a note you wrote before you started, saying: “if you get this far and go wrong, you are already this many digits into a fresh attempt.”

3Rabin-Karp and rolling hashes

Compare numbers instead of strings. Cheap, probabilistic, and unbeatable when you are searching for many patterns at once.

Comparing two length-m strings costs O(m). Comparing two integers costs O(1). So hash the pattern once, hash each window of the text, and only compare strings when the hashes agree.

The trick is computing the next window's hash from the current one in constant time. Treat the window as a number in base B:

rolling.py

#   hash(A) = a*B^2 + b*B^1 + c*B^0     (mod M)
#
# To slide from B to C:
#   drop  a * B^2
#   multiply by B      -> b*B^2 + c*B^1
#   add   d
#
# One multiply, one subtract, one add. O(1) per position.

rabin_karp.py

def rabin_karp(text, pat, B=256, M=1_000_000_007):
    n, m = len(text), len(pat)
    if m == 0:
        return 0
    if m > n:
        return -1

    high = pow(B, m - 1, M)              # B^(m-1) mod M, precomputed
    hp = ht = 0
    for i in range(m):                   # hash the pattern and the first window
        hp = (hp * B + ord(pat[i])) % M
        ht = (ht * B + ord(text[i])) % M

    for i in range(n - m + 1):
        if hp == ht and text[i:i + m] == pat:   # verify! hashes can collide
            return i
        if i < n - m:                            # roll the window
            ht = ((ht - ord(text[i]) * high) * B + ord(text[i + m])) % M

    return -1

Always verify the match

Equal hashes do not mean equal strings. Skipping the text[i:i+m] == pat check turns a correct algorithm into one that is usually right, which is worse than one that is obviously wrong.

With a good modulus, collisions are rare enough that the verification almost never runs, so it costs nothing on average. The worst case is still O(n·m) — and an adversary who knows your B and M can construct it, which is why competitive programmers randomise both.

Checking suitcases by weight

You are looking for one particular suitcase on a carousel. Opening each one is slow, so you weigh them instead: any suitcase whose weight is wrong is definitely not yours, and you skip it instantly.

A suitcase with the right weight might be yours, so you open that one to check. Weighing is the hash; opening is the verification; and two different suitcases weighing the same is a collision.

	KMP	Rabin-Karp
Worst case	O(n + m), guaranteed	O(n·m) with adversarial input
Average case	O(n + m)	O(n + m)
Extra space	O(m) for the table	O(1)
Many patterns at once	One pass each	One pass total — hash them into a set
2-D / substring problems	Awkward	Natural
Streaming input	Yes	Yes

That fourth row is the reason Rabin-Karp survives despite its worse guarantee. Searching for k patterns of the same length costs one pass and a set lookup per position; that is how plagiarism detectors and rsync-style delta algorithms work. (For many patterns of different lengths the specialist answer is Aho–Corasick, which is KMP generalised to a trie — the structure from Chapter 18.)

4Palindromes and windows

Two techniques that come up constantly and need no precomputed table at all.

Expand around centres. A palindrome is defined by its centre, and a string of length n has 2n - 1 possible centres — n characters and n - 1 gaps between them. Try each, expanding outwards while the characters match:

palindrome.pyO(n²) time, O(1) space

def longest_palindrome(s):
    if not s:
        return ""
    best_lo, best_len = 0, 1

    def expand(lo, hi):
        nonlocal best_lo, best_len
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            lo -= 1
            hi += 1
        # the loop overshoots by one on each side
        if hi - lo - 1 > best_len:
            best_len = hi - lo - 1
            best_lo = lo + 1

    for centre in range(len(s)):
        expand(centre, centre)        # odd length:  a[b]a
        expand(centre, centre + 1)    # even length: ab|ba

    return s[best_lo:best_lo + best_len]

The two centre kinds

Forgetting even-length centres is the standard bug, and it is invisible on most examples — "racecar" works fine and "abba" silently returns "a".

There is an O(n) algorithm (Manacher's) which reuses information from palindromes already found, in much the same spirit as KMP. It is worth knowing exists; it is rarely worth writing.

Sliding count windows. Anagram and permutation questions almost never need sorting. Keep a count of the characters in a window of fixed size, and update it in O(1) as the window moves:

anagrams.py

from collections import Counter

def find_anagrams(text, pat):
    """All start indices where a permutation of pat occurs in text."""
    m = len(pat)
    if m == 0 or m > len(text):
        return []

    need = Counter(pat)
    window = Counter(text[:m])
    out = [0] if window == need else []

    for i in range(m, len(text)):
        window[text[i]] += 1                  # character entering on the right
        left = text[i - m]
        window[left] -= 1                     # character leaving on the left
        if window[left] == 0:
            del window[left]                  # keep the dict small so == is cheap
        if window == need:
            out.append(i - m + 1)

    return out

Delete the zeros

del window[left] when a count reaches zero is not tidiness — it is what makes window == need correct and fast. A Counter holding {'a': 0} does not compare equal to one without the key at all in older Pythons, and either way the dictionary grows to the size of the alphabet and every comparison scans it.

The alternative used in tight code is a single matched counter: track how many distinct characters currently have exactly the right count, and compare that against len(need). That makes each step genuinely O(1) rather than O(alphabet).

5Choosing, and what lies beyond

Five questions that pick the algorithm, and a short list of the specialist structures.

Situation	Use
One search, ordinary text	`str.find` — your language's built-in is written in C
Guaranteed linear time needed	KMP
Many patterns, same length	Rabin-Karp with a set of hashes
Many patterns, different lengths	Aho–Corasick (a trie plus failure links)
Many searches in one fixed text	Suffix array or suffix automaton, built once
Longest repeated / common substring	Suffix array + LCP array
Approximate matching	Edit-distance DP (Chapter 26)
Palindromes	Expand around centres; Manacher if you must have O(n)

The honest first answer

In production, use the built-in. CPython's str.find uses a hybrid of Boyer-Moore and Horspool with a Bloom-filter skip table, written in C, and it will beat your KMP by a large constant factor.

Learn KMP because the failure function is a genuinely useful idea that reappears in Aho–Corasick, in Z-functions, and in the “shortest repeating unit” trick below — not because you will hand-roll substring search.

Two small results that fall straight out of the failure function, and are worth carrying:

The shortest repeating unit. For a string s of length n, let L = lps[n-1]. If n % (n - L) == 0, then s is exactly n / (n - L) copies of its first n - L characters. One table, no search.
Counting all occurrences (including overlapping ones) is KMP with k = lps[k - 1] instead of a return when a match completes. Overlapping matches come for free; the naive algorithm has to be told about them explicitly.

Boyer-Moore reads backwards

The algorithm your language actually uses does something the two above do not: it compares the pattern right to left.

If the pattern is "NEEDLE" and the character sitting under its last position is X — which appears nowhere in the pattern — then no alignment overlapping that X can possibly match, and you may skip forward by the whole pattern length in one step. On long patterns and large alphabets it reads fewer characters than the text contains, which is why it wins in practice despite a worse theoretical bound.

What to carry forward

Naive matching is O(n·m) in the worst case, and the killer input is a long run of one repeated character.
KMP precomputes lps[i] = the longest proper prefix of pat[0..i] that is also a suffix.
The fallback is length = lps[length - 1], never length = 0. Building the table is KMP run on the pattern against itself.
KMP is O(n + m) because k rises at most n times in total, so it can fall at most n times — an amortised argument, like array doubling.
Rabin-Karp rolls a hash over the text in O(1) per step. Equal hashes must still be verified by comparing the strings.
Rabin-Karp's edge is many patterns at once: hash them into a set and make one pass.
Palindromes: expand around all 2n-1 centres. Forgetting the even-length centres is the standard bug.
Anagram windows: keep a character count and update it in O(1) as the window slides. Delete keys whose count reaches zero.
lps[n-1] gives the shortest repeating unit for free: if n % (n - L) == 0, the string is a repeated block.
In production use the built-in find. Learn KMP for the failure function, which reappears in Aho–Corasick and elsewhere.

>_Playground

Naive versus KMP on the killer input, a rolling hash rolling, and the failure function's hidden uses.

scratch.pypython not loaded

import time
from collections import Counter

# ---- the input that destroys naive matching ---------------------------------
def find_naive(text, pat):
    n, m = len(text), len(pat)
    comps = 0
    for shift in range(n - m + 1):
        k = 0
        while k < m and text[shift + k] == pat[k]:
            k += 1; comps += 1
        if k < m:
            comps += 1
        if k == m:
            return shift, comps
    return -1, comps

def build_lps(pat):
    lps = [0] * len(pat)
    length, i = 0, 1
    while i < len(pat):
        if pat[i] == pat[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, pat):
    if not pat:
        return 0, 0
    lps = build_lps(pat)
    k = 0; comps = 0
    for i, ch in enumerate(text):
        while k and ch != pat[k]:
            k = lps[k - 1]; comps += 1
        comps += 1
        if ch == pat[k]:
            k += 1
        if k == len(pat):
            return i - len(pat) + 1, comps
    return -1, comps

TEXT = "A" * 30000 + "B"
PAT = "A" * 500 + "B"

t = time.perf_counter(); i1, c1 = find_naive(TEXT, PAT); t1 = time.perf_counter() - t
t = time.perf_counter(); i2, c2 = kmp_search(TEXT, PAT); t2 = time.perf_counter() - t
t = time.perf_counter(); i3 = TEXT.find(PAT);            t3 = time.perf_counter() - t

print(f"text: 30,001 characters   pattern: 501 characters")
print(f"  naive     : index {i1}  {c1:>12,} comparisons  {t1:.3f}s")
print(f"  KMP       : index {i2}  {c2:>12,} comparisons  {t2:.3f}s")
print(f"  str.find  : index {i3}  {'(C code)':>12}       {t3:.5f}s")
print(f"  all agree : {i1 == i2 == i3}")

# ---- the failure function, spelled out ---------------------------------------
P = "ABABCABAB"
lps = build_lps(P)
print()
print("failure function for", P)
print("  i        :", "  ".join(f"{i}" for i in range(len(P))))
print("  pat[i]   :", "  ".join(P))
print("  lps[i]   :", "  ".join(str(x) for x in lps))
for i, v in enumerate(lps):
    if v:
        print(f"    pat[0:{i+1}] = {P[:i+1]:<10} its {v}-character prefix {P[:v]!r} "
              f"is also its suffix")

# ---- the shortest repeating unit falls out for free --------------------------
def repeating_unit(s):
    n = len(s)
    if n == 0:
        return ""
    L = build_lps(s)[-1]
    unit = n - L
    return s[:unit] if n % unit == 0 else s

print()
for s in ["abcabcabc", "aaaa", "abcd", "ababab", "abaaba", "xyzxyzxyzxyz"]:
    u = repeating_unit(s)
    print(f"  {s:<14} -> unit {u!r} repeated {len(s)//len(u)} times")

# ---- all occurrences, including overlapping ones ----------------------------
def find_all(text, pat):
    if not pat:
        return []
    lps = build_lps(pat)
    out, k = [], 0
    for i, ch in enumerate(text):
        while k and ch != pat[k]:
            k = lps[k - 1]
        if ch == pat[k]:
            k += 1
        if k == len(pat):
            out.append(i - k + 1)
            k = lps[k - 1]          # <- instead of returning
    return out

print()
print("overlapping matches of 'aa' in 'aaaa'   :", find_all("aaaa", "aa"))
print("matches of 'aba' in 'abababa'           :", find_all("abababa", "aba"))
print("str.find would report only the first    :", "abababa".find("aba"))

# ---- Rabin-Karp, and a deliberate collision ---------------------------------
def rk_hashes(text, m, B=256, M=101):
    """A deliberately tiny modulus, so collisions actually happen."""
    n = len(text)
    if m > n: return []
    high = pow(B, m - 1, M)
    h = 0
    for i in range(m):
        h = (h * B + ord(text[i])) % M
    out = [(0, h)]
    for i in range(n - m):
        h = ((h - ord(text[i]) * high) * B + ord(text[i + m])) % M
        out.append((i + 1, h))
    return out

S = "the quick brown fox jumps over the lazy dog"
hs = rk_hashes(S, 3)
buckets = {}
for i, h in hs:
    buckets.setdefault(h, []).append(S[i:i+3])
collisions = {h: v for h, v in buckets.items() if len(set(v)) > 1}
print()
print(f"3-character windows of a 43-character string, hashed mod 101:")
print(f"  distinct windows : {len(set(S[i:i+3] for i, _ in hs))}")
print(f"  distinct hashes  : {len(buckets)}")
print(f"  colliding hashes : {len(collisions)}")
for h, v in list(collisions.items())[:3]:
    print(f"    hash {h:>3} shared by {sorted(set(v))}")
print("  ...which is exactly why the string comparison after a hash match is not optional.")

# ---- palindromes and anagram windows ----------------------------------------
def longest_palindrome(s):
    if not s: return ""
    lo, ln = 0, 1
    def expand(a, b):
        nonlocal lo, ln
        while a >= 0 and b < len(s) and s[a] == s[b]:
            a -= 1; b += 1
        if b - a - 1 > ln:
            ln = b - a - 1; lo = a + 1
    for c in range(len(s)):
        expand(c, c); expand(c, c + 1)
    return s[lo:lo + ln]

print()
for s in ["babad", "cbbd", "forgeeksskeegfor", "abba", "a", "abcde"]:
    print(f"  longest palindrome in {s!r:<20} = {longest_palindrome(s)!r}")

def find_anagrams(text, pat):
    m = len(pat)
    if m == 0 or m > len(text): return []
    need, win = Counter(pat), Counter(text[:m])
    out = [0] if win == need else []
    for i in range(m, len(text)):
        win[text[i]] += 1
        left = text[i - m]
        win[left] -= 1
        if win[left] == 0:
            del win[left]
        if win == need:
            out.append(i - m + 1)
    return out

print()
print("anagrams of 'abc' in 'cbaebabacd' at:", find_anagrams("cbaebabacd", "abc"))
print("anagrams of 'ab'  in 'abab'        at:", find_anagrams("abab", "ab"))

Real Python, running in your browser. Nothing is installed or uploaded.

Output appears here. The first run takes a few seconds while Python loads.

✓Exercises

Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.

All Warm-up Core Challenge Reset chapter

Chapter 29 — Advanced Structures: Segment Trees, Fenwick, LRU, Bloom

Four structures that show up the moment scale gets serious: range queries with updates, an O(1) cache, and a filter that is allowed to be wrong in exactly one direction.

Continue →