Exact String Matching

Given text of length n and pattern of length m, exact matching reports every position where the pattern occurs without mismatches.

Naive matching

Try every alignment and compare symbols until a mismatch. Worst-case time is O((n - m + 1)m), or O(nm), and auxiliary space is O(1). It is often adequate for short patterns or small inputs.

Knuth–Morris–Pratt

KMP preprocesses the pattern into a longest-proper-prefix-that-is-also-suffix table. After a mismatch, the table identifies how much matched structure can be reused without moving the text index backward.

Preprocessing costs Θ(m) and scanning costs Θ(n), for Θ(n + m) total time and Θ(m) auxiliary space. Correctness follows from the prefix invariant: the current matched prefix is also a suffix of the text processed so far, and the failure transition chooses the longest smaller prefix that could still match.

Rabin–Karp

Rabin–Karp compares rolling hashes for each window, then verifies characters when hashes match. With a suitable hash model it has expected O(n + m) time, but collisions can produce O(nm) verification work. Never treat hash equality as proof of string equality unless the application accepts probabilistic error.

Boyer–Moore family

Right-to-left comparison plus bad-character and good-suffix shifts can skip large regions and performs well for many practical texts. Variants have different preprocessing and worst-case guarantees, so name the exact variant when stating a bound.

Java considerations

String indices address UTF-16 code units. Searching arbitrary human-perceived characters may require code-point iteration, normalization, or a text library. For ordinary substring lookup, prefer the tested standard API unless studying or needing a specialized matching algorithm.

Exercises

1. Build the KMP prefix table for ABABACA.
2. Construct a worst case for naive matching.
3. Explain why rolling-hash matches require verification.