String matching finds all occurrences of a pattern P (length m) inside a text T (length n).

• Naive scan — O(n·m).
• This unit’s algorithms — KMP and the Z-algorithm are linear in every case (O(n + m)); Boyer-Moore and Rabin-Karp are linear on typical inputs (O(n + m) average) while sharing the naive scan’s O(n·m) worst case. All of them remember what earlier comparisons already proved, so no character is ever re-compared wastefully.

The Naive Baseline

Compare the pattern against every text position and, on a mismatch, restart from the next position. When a long prefix of the pattern matches, each failed shift re-does nearly all of the previous work:

T = AAAAAAAAAAAAAAAAAB     (n = 17)
P = AAAAB                  (m = 5)
→ every shift fails on the last character: 13 shifts × 5 compares = 65

Worst case is O(n·m). For a real workload — searching a several-megabyte log file for a short token — that quadratic blowup is the difference between an interactive result and a hang. Still, the naive loop is the right default for short patterns and small texts, because its constant factor is tiny.

The Shared Insight: Reuse What the Comparisons Proved

Every linear-time matcher exploits one observation: when a mismatch occurs at pattern position j, the prefix P[0..j-1] has already matched the text.

The pattern’s internal structure tells us exactly how much of that match can be reused, so the text cursor never moves backward. KMP, Rabin-Karp, and the Z-algorithm are three different ways to encode and exploit that fact.

KMP — the Prefix (LPS) Table

KMP precomputes a failure table (longest-proper-prefix-suffix, LPS): lps[j] is the length of the longest proper prefix of P[0..j] that is also a suffix. On a mismatch at j, instead of starting over we resume at j = lps[j-1] — those characters are already known to match. The table is computed in one left-to-right pass over the pattern:

P   = a b a b c a b a b
lps = 0 0 1 2 0 1 2 3 4

Building the table is O(m), scanning the text is O(n), so the total is O(n + m) with O(m) extra space. KMP’s only hidden cost is the constant factor of following the table on every mismatch.

Rabin-Karp — Hashing the Window

Instead of comparing characters, Rabin-Karp hashes the pattern and every length-m window of the text with a polynomial rolling hash, so each window’s hash follows from the previous one in O(1):

hash(w) = (c_0·d^(m-1) + c_1·d^(m-2) + ... + c_(m-1)) mod q

A match is confirmed only when the window hash equals the pattern hash, keeping false positives negligible for a good prime modulus.

• Worst case — still O(n·m) (pathological collisions).
• Average case — O(n + m) with O(1) extra space.

Its real superpower is multi-pattern search: one window hash can be looked up against a dictionary of pattern hashes in a single step — the basis of duplicate detection and plagiarism tooling.

The Z-Algorithm — the Z-box Invariant

Over the string S = P$T (with a separator that appears in neither), z[i] is the length of the longest substring starting at i that matches the prefix of S. When i lies inside the current rightmost matching box [l, r], seed z[i] from z[i - l] and extend outward; because the box’s right edge only moves right, total work is O(n). The Z-array is a reusable primitive that reappears in Manacher’s palindrome algorithm and in search-index tooling.

Aho-Corasick — Many Patterns at Once

Rabin-Karp handles multi-pattern search in the average case; Aho-Corasick makes it a hard guarantee: O(n + m + k) where n is the text length, m is the sum of all pattern lengths, and k is the total number of matches found. It is the algorithm behind grep -F with multiple patterns, intrusion-detection signatures, and dictionary/blacklist screening.

Build phase (O(m) time, O(m) space): insert every pattern into a trie, then augment each node with a failure link — a pointer to the longest proper suffix of that node’s string that is itself a trie node. Fail links are computed in a breadth-first pass over the trie:

patterns = he, she, his, hers

         root
        /    \
      h(1)    s(2)
     /         \
    e(3)       h(4)
     \        /  \
     r(5)   e(6)  i(7)
       \               \      (fail links dashed)
       s(8) ----------> s(2)

Scan phase (O(n + k)): walk the text through the trie one character at a time. On a match, follow the output links (a linked list of all dictionary words ending here) to emit every pattern; on a mismatch, follow the failure link instead of restarting — the text cursor never moves backward, exactly like KMP’s LPS table but generalized to a trie. The failure links are the trie-flavored version of the “reuse what the comparisons proved” insight.

Aho-Corasick beats Rabin-Karp whenever the pattern set is large or the match count can be high (an IDS scanning traffic against 10,000 signatures). Its cost is more setup memory than Rabin-Karp’s single hash set.

Choosing an Algorithm

Worked Example

Search P = "ababcabab" in T = "abxababcababyz". Build lps = [0,0,1,2,0,1,2,3,4], then scan:

i    compare            action
0-1  a, b              P[0], P[1] match → j=2
2    x vs P[2]=a       mismatch → j=lps[1]=0, still mismatch → move on
3    a b a b c a b a b P[0..8] all match → j=9: match at i=3
12   y vs P[4]=c       mismatch → j=lps[3]=2, then j=0
13   z vs P[0]=a       mismatch → done

The naive scan would have re-compared from shifts 1 and 2; KMP’s table skips both. Total work is one pass over the text plus the table build — O(n + m).

Practice Trajectory

1. Implement the naive matcher and count comparisons on the worst-case AAAA...B input.
2. Implement the LPS table builder and verify it against ababac, aaaab, and abcabca.
3. Implement KMP and confirm match positions against a brute-force oracle on random strings.
4. Implement Rabin-Karp with a collision-prone modulus, then a large prime, and observe the false-positive behavior.
5. Compute the Z-array for ab$ababcabab by hand, then convert one algorithm into the other and confirm identical matches.
6. Build an Aho-Corasick trie for he/she/his/hers and trace the failure links against the text ushers.

When It’s the Right Tool