11.2 String Matching
Prerequisites: Binary Search and Hash Tables. Throughout this section, we adopt the following convention: the first occurrence of an empty pattern in any text is at position 0; if no match is found, the result is -1. In Java, indices are computed based on UTF-16 code units.
Logs Are Not Ordered Arrays
This page explores three approaches:
- Naive matching: maintains the simplest, most easily verifiable baseline;
- Rabin–Karp: uses rolling hashes to filter candidate windows, then verifies each one character by character;
- KMP: computes jump positions after a mismatch using information from the pattern itself, allowing the text pointer to advance without backtracking.
The final Trie solution addresses a different class of problem: instead of searching for a pattern within a text, it enables lookup of full words or common prefixes among a set of words.
A Compilable Implementation
String parameters must be non-null; otherwise the methods throw NullPointerException. Window loops use start <= n-m, avoiding overflow of start+m near the end of a very long string. Trie operations validate the entire input before visiting or creating nodes, so an invalid suffix cannot leave a partial path behind.
import java.util.Objects;
public final class StringMatchingDemo {
private static final long BASE = 65_536;
private static final long MOD = 1_000_000_007L;
private StringMatchingDemo() {}
static int naiveSearch(String text, String pattern) {
Objects.requireNonNull(text, "text");
Objects.requireNonNull(pattern, "pattern");
int n = text.length();
int m = pattern.length();
if (m == 0) {
return 0;
}
for (int start = 0; start <= n - m; start++) {
int matched = 0;
while (matched < m
&& text.charAt(start + matched) == pattern.charAt(matched)) {
matched++;
}
if (matched == m) {
return start;
}
}
return -1;
}
static int rabinKarp(String text, String pattern) {
Objects.requireNonNull(text, "text");
Objects.requireNonNull(pattern, "pattern");
int n = text.length();
int m = pattern.length();
if (m == 0) {
return 0;
}
if (m > n) {
return -1;
}
long highestPlace = 1;
long patternHash = 0;
long windowHash = 0;
for (int index = 0; index < m - 1; index++) {
highestPlace = highestPlace * BASE % MOD;
}
for (int index = 0; index < m; index++) {
patternHash = (patternHash * BASE + pattern.charAt(index)) % MOD;
windowHash = (windowHash * BASE + text.charAt(index)) % MOD;
}
for (int start = 0; start <= n - m; start++) {
if (windowHash == patternHash
&& text.regionMatches(start, pattern, 0, m)) {
return start;
}
if (start < n - m) {
long outgoing = text.charAt(start) * highestPlace % MOD;
windowHash = (windowHash - outgoing + MOD) % MOD;
windowHash = (windowHash * BASE + text.charAt(start + m)) % MOD;
}
}
return -1;
}
static int[] prefixFunction(String pattern) {
int[] prefix = new int[pattern.length()];
for (int index = 1, length = 0; index < pattern.length(); index++) {
while (length > 0
&& pattern.charAt(index) != pattern.charAt(length)) {
length = prefix[length - 1];
}
if (pattern.charAt(index) == pattern.charAt(length)) {
length++;
}
prefix[index] = length;
}
return prefix;
}
static int kmpSearch(String text, String pattern) {
Objects.requireNonNull(text, "text");
Objects.requireNonNull(pattern, "pattern");
if (pattern.isEmpty()) {
return 0;
}
int[] prefix = prefixFunction(pattern);
for (int textIndex = 0, matched = 0;
textIndex < text.length();
textIndex++) {
while (matched > 0
&& text.charAt(textIndex) != pattern.charAt(matched)) {
matched = prefix[matched - 1];
}
if (text.charAt(textIndex) == pattern.charAt(matched)) {
matched++;
if (matched == pattern.length()) {
return textIndex - matched + 1;
}
}
}
return -1;
}
static final class Trie {
private final Trie[] children = new Trie[26];
private boolean terminal;
void insert(String word) {
validate(word);
Trie node = this;
for (int index = 0; index < word.length(); index++) {
int slot = slot(word.charAt(index));
if (node.children[slot] == null) {
node.children[slot] = new Trie();
}
node = node.children[slot];
}
node.terminal = true;
}
boolean contains(String word) {
Trie node = findPrefix(word);
return node != null && node.terminal;
}
boolean startsWith(String prefix) {
return findPrefix(prefix) != null;
}
private Trie findPrefix(String value) {
validate(value);
Trie node = this;
for (int index = 0; index < value.length(); index++) {
node = node.children[slot(value.charAt(index))];
if (node == null) {
return null;
}
}
return node;
}
private static void validate(String value) {
for (int index = 0; index < value.length(); index++) {
slot(value.charAt(index));
}
}
private static int slot(char value) {
if (value < 'a' || value > 'z') {
throw new IllegalArgumentException(
"this trie accepts lowercase ASCII letters only");
}
return value - 'a';
}
}
public static void main(String[] args) {
String text = "AABAACAADAABAAABAA";
String pattern = "AABA";
assert naiveSearch(text, pattern) == 0;
assert rabinKarp(text, pattern) == 0;
assert kmpSearch(text, pattern) == 0;
assert naiveSearch("ABABABACABA", "ABABAC") == 2;
assert rabinKarp("ABABABACABA", "ABABAC") == 2;
assert kmpSearch("ABABABACABA", "ABABAC") == 2;
assert kmpSearch("abc", "") == 0;
assert rabinKarp("short", "longer") == -1;
Trie trie = new Trie();
trie.insert("app");
trie.insert("apple");
trie.insert("application");
assert trie.contains("app");
assert !trie.contains("appl");
assert trie.startsWith("appl");
assert trie.startsWith("");
System.out.println("Three matching results are consistent");
}
}Run:
javac StringMatchingDemo.java
java -ea StringMatchingDemoAfter the assertions pass, the program prints Three matching results are consistent.
Rabin–Karp: Hash Match Still Requires Verification
A hash for a window of length m can be expressed as:
c0 * BASE^(m-1) + c1 * BASE^(m-2) + ... + c(m-1)Each step is reduced modulo MOD. Moving the window right subtracts the outgoing code unit's high-place contribution, multiplies by BASE, then adds the incoming code unit. BASE=65536 covers the full char range; products using these constants fit in long. For 0<m<=n, preprocessing the pattern and first window takes O(m), and each later hash update takes O(1).
Different strings can produce the same modular hash, so a hash match only indicates that "further verification is warranted." The code uses regionMatches to perform character-by-character comparison, ensuring that hash collisions do not result in incorrect answers. With c equal-hash candidate windows, the upper bound is O(n+m+c*m); a verification may also stop early on a differing character. Expected O(n+m) requires an additional input or randomized-hash model that controls total verification work. This example fixes BASE and MOD and gives no randomization guarantee; worst-case time remains O(nm). Therefore, this educational exposition of rolling hash should not be considered a secure hash function in contexts involving adversarial input, cryptography, or integrity protection.
KMP: How Long to Preserve a Prefix After a Mismatch
For the pattern ABABAC, the prefix function is:
pattern: A B A B A C
prefix: 0 0 1 2 3 0prefix[i] represents the length of the longest proper prefix of pattern[0..i] that is also a suffix. If the first matched characters match but fail at the next position, there's no need to backtrack the text pointer. Instead, simply update matched to prefix[matched-1] and continue checking against a shorter, still plausible boundary.
Both the construction of the prefix function and the text scanning follow the same "pointer only advances, failure length gradually shrinks" pattern, resulting in a total time complexity of O(n+m) and additional space usage of O(m). Each successful comparison increases the matched length by at most 1, and each fallback strictly decreases it. Total fallback distance is bounded by earlier increases. That is why the nested while does not imply quadratic time. KMP provides a deterministic linear bound, though it does not guarantee faster performance than standard libraries on all short strings.
Trie: Prefix Queries Are Another Contract
A Trie breaks words into edges, sharing common prefixes. contains("app") requires that the path exists and ends with a marker indicating a complete word; startsWith("app") only requires that the path exists. These two conditions cannot be interchanged.
This page aims to clarify the indexing relationships and only accepts a..z, where each node maintains fixed references to 26 child nodes. It validates the entire string first, so even an immediate prefix miss costs O(m+1) time, where m is the input length. If inserted words contain L characters in total, there are at most L+1 nodes, including the root. With P actual prefix nodes and 26 slots per node, storage is Θ(26P), or Θ(P) for a fixed alphabet. The actual byte count is influenced by JVM overhead, object headers, reference sizes, and alignment, so it cannot be derived from a fixed "26 slots" value. For a large alphabet or sparse branching, maps can avoid reserving slots for absent branches. They also add hashing, container objects, and different access constants, so the memory tradeoff depends on branch density.
The empty prefix always exists: even an empty dictionary has startsWith("") == true. contains("") becomes true only after inserting the empty word. Repeated insertion adds no extra word record. Invalid characters consistently raise IllegalArgumentException, even if an earlier prefix is absent.
In Java, char is a UTF-16 code unit. In "😀x", x has Java index 2 rather than code-point index 1. If product contracts are matched based on Unicode code points, user-perceived characters, or normalized text, a consistent encoding and normalization strategy must be established upfront. It is not valid to directly treat charAt indices as character positions across all languages.
Complexity and Choice
| Method | Time | Extra Space | Suitable Problems |
|---|---|---|---|
| Naive Matching | Worst-case O(nm) | O(1) | Short patterns, baseline validation |
| Rabin–Karp | O(n+m+c*m) for c hash candidates; worst O(nm) | O(1) | Sliding window, multi-pattern hashing extensions |
| KMP | O(n+m) | O(m) | Single pattern, streaming or deterministic linear requirements |
| Trie | Each operation O(m+1) | Θ(P) storage; O(1) query auxiliary space | Dictionaries, prefix queries |
All three searches handle an empty pattern in constant time. If the pattern is longer than the text, naive search and Rabin–Karp fail immediately; KMP still builds its prefix table. This KMP function accepts a complete String; a streaming version must preserve matched and cumulative position between chunks. See Princeton substring search and Tries.
Engineering code should first clarify the semantics and performance boundaries of standard library functions. Java String.indexOf already provides substring search; the value of algorithmic documentation lies in understanding when existing work can be reused, not in requiring business code to reimplement solutions.
Check Mismatches and Prefixes
- Manually compute the prefix function for
AAAA,ABABAC, andaabaaab. - Generate random short strings for the three search patterns and compare them against
String.indexOf. - Build a small-modulus Rabin–Karp algorithm and deliberately induce hash collisions to verify that character-by-character comparison still rejects false positives.
- Add deletion functionality to the Trie. Under what conditions can shared-prefix nodes be safely reclaimed?
- To support case-insensitive Unicode text, what additional normalization steps are missing from the input contract?
Simple matching provides the most trustworthy baseline. Rabin–Karp uses hashing to filter candidates, but must verify against hash collisions. KMP encodes known prefix-suffix relationships within its jump table. Trie shifts the problem from "searching for a pattern in text" to "looking up a prefix in a dictionary."
The next chapter continues the practice of narrowing the problem: first, see how Divide and Conquer breaks down independent subproblems, then how Backtracking systematically explores possible choices.