String Matching Algorithms

Why This Matters

String matching is one of the most fundamental problems in computer science, appearing everywhere from text editors and search engines to DNA sequence analysis and plagiarism detection. When you're tested on these algorithms, you're really being evaluated on your understanding of preprocessing strategies, amortized analysis, space-time tradeoffs, and heuristic optimization. These concepts extend far beyond strings—they're core algorithmic design principles you'll encounter throughout your career.

Don't just memorize the time complexities for each algorithm. Instead, focus on why each approach achieves its efficiency: What information does preprocessing capture? How does the algorithm avoid redundant work? When does one technique outperform another? Understanding these mechanisms will help you tackle FRQ-style questions that ask you to analyze, compare, or apply these algorithms to novel scenarios.

---

Brute Force Approaches

The simplest strategy checks every possible alignment between pattern and text. While inefficient, understanding this baseline helps you appreciate what more sophisticated algorithms optimize.

Naive String Matching Algorithm

• Compares pattern against every position in text—slides the pattern one character at a time, checking all $m$ characters at each of $n - m + 1$ positions
• Time complexity of $O(m \cdot n)$ in the worst case, where $m$ is pattern length and $n$ is text length
• No preprocessing required—makes it useful for one-time searches on small inputs or as a baseline for understanding optimization gains

---

Preprocessing the Pattern

These algorithms invest upfront computation to build auxiliary data structures from the pattern, enabling smarter comparisons that skip redundant work. The key insight: information about the pattern's internal structure tells us where mismatches can't possibly lead to matches.

Knuth-Morris-Pratt (KMP) Algorithm

• Builds a Longest Prefix-Suffix (LPS) array in $O(m)$ time—captures how the pattern overlaps with itself to avoid re-examining characters
• Achieves $O(m + n)$ time complexity—never backtracks in the text, making it optimal for streaming applications
• Exploits partial match information—when a mismatch occurs, the LPS array indicates exactly where to resume comparison

Z Algorithm

• Computes the Z-array where $Z[i]$ stores the length of the longest substring starting at position $i$ that matches a prefix of the string
• Linear $O(n + m)$ time complexity—concatenates pattern and text with a sentinel character, then processes in a single pass
• Particularly elegant for multiple pattern problems—the Z-array provides direct information about all occurrences without additional bookkeeping

Finite Automata for String Matching

• Constructs a deterministic finite automaton (DFA) with states representing how much of the pattern has been matched
• Text processing runs in $O(n)$ time after $O(m \cdot |\Sigma|)$ preprocessing, where $|\Sigma|$ is alphabet size
• Guarantees single-pass, deterministic behavior—each character triggers exactly one state transition, making it ideal for hardware implementations

---

Heuristic Optimization

Rather than just avoiding redundant comparisons, these algorithms use clever heuristics to skip large portions of the text entirely. The insight: sometimes we can prove that many positions are impossible matches without examining them.

Boyer-Moore Algorithm

• Uses two heuristics: bad character and good suffix rules—when a mismatch occurs, calculates the maximum safe shift from both rules and takes the larger
• Best-case time complexity of $O(n/m)$—achieves sublinear performance by potentially skipping $m$ characters per comparison
• Most effective with large alphabets and long patterns—the bad character rule becomes more powerful when mismatched characters are unlikely to appear elsewhere in the pattern

---

Hash-Based Methods

Hashing transforms the comparison problem: instead of checking characters one by one, we compare fixed-size hash values. The tradeoff: we gain speed but introduce the possibility of false positives from hash collisions.

Rabin-Karp Algorithm

• Uses rolling hash functions to compute substring hashes in $O(1)$ time per position after initial $O(m)$ computation
• Average time complexity of $O(n + m)$ but degrades to $O(m \cdot n)$ when many hash collisions occur, requiring character-by-character verification
• Excels at multiple pattern matching—can search for $k$ patterns simultaneously by storing all pattern hashes in a hash table

---

Advanced Data Structures

When you need to perform many searches on the same text, preprocessing the text (not just the pattern) becomes worthwhile. These structures trade significant preprocessing time and space for extremely fast queries.

Suffix Trees and Arrays

• Suffix trees enable $O(m)$ pattern matching after $O(n)$ construction—store all suffixes in a compressed trie structure
• Suffix arrays offer a space-efficient alternative requiring $O(n \log n)$ construction time but only $O(n)$ space versus $O(n)$ pointers in suffix trees
• Support powerful string operations beyond matching—longest common substring, longest repeated substring, and string statistics all become efficient queries

---

Quick Reference Table

---

Self-Check Questions

1. Which two algorithms both achieve $O(n + m)$ time through pattern preprocessing but use fundamentally different auxiliary arrays? What does each array capture about the pattern?

2. An exam question states: "The algorithm achieves sublinear time in the best case." Which algorithm is being described, and what conditions enable this performance?

3. Compare and contrast Rabin-Karp and KMP: Under what circumstances would you choose each? What's the key tradeoff between them?

4. You need to search for the same pattern millions of times in a fixed text corpus. Which approach would you use, and why is it better than running KMP repeatedly?

5. A system processes streaming text character-by-character and must identify pattern matches in real-time without buffering. Which algorithms are suitable, and which are not? Justify your answer based on how each algorithm processes input.