String Matching Algorithms — KMP, Rabin-Karp, & Suffix Arrays Explained | Chapter 32 in Introduction to Algorithms

Chapter 32 of Introduction to Algorithms tackles the fundamental problem of string matching — finding all occurrences of a pattern string P within a larger text string T. This topic underlies critical applications in text search, data compression, bioinformatics, and pattern recognition. The chapter presents a spectrum of algorithms including the naive method, Rabin-Karp, finite automata, Knuth-Morris-Pratt (KMP), and suffix arrays, each offering different trade-offs between preprocessing complexity and matching efficiency.

Watch the video above for a guided breakdown of each algorithm and when to use them. Subscribe to Last Minute Lecture for more textbook-based algorithm tutorials.

Naive String-Matching Algorithm

The naive approach checks for a match of the pattern P at every possible shift within T. For each shift s, it compares P[1 to m] to T[s+1 to s+m]. Though its worst-case runtime is O((n – m + 1) × m), it performs reasonably well on average, especially with random inputs or distinct characters. It also serves as a baseline to evaluate the performance of more sophisticated methods.

Rabin-Karp Algorithm: Hash-Based Matching

Rabin-Karp uses a rolling hash function to convert substrings of T and the pattern P into numerical hash values. It compares hashes first — only verifying the actual strings if a hash match is found. Key features include:

• Efficient average-case performance
• Rolling hash computation in constant time
• Ideal for multiple pattern matching and 2D string searches

Its worst-case runtime remains O((n – m + 1) × m), but average performance can be excellent with a well-chosen prime modulus.

Finite Automaton String Matching

This method builds a deterministic finite automaton (DFA) that recognizes the pattern P. The automaton uses:

• A finite set of states
• A transition function based on the suffix function σ(x)
• Start and accept states

After preprocessing time of O(m × |alphabet|), the algorithm scans the text in linear time O(n). While it is efficient during matching, constructing the transition function can be complex for large alphabets.

KMP Algorithm: Efficient Exact Matching

The Knuth-Morris-Pratt (KMP) algorithm improves on naive matching by using a prefix function π to avoid redundant comparisons after a mismatch. π[q] stores the length of the longest prefix of P[1 to q] that is also a suffix, allowing the pattern to shift efficiently after mismatches.

• Preprocessing: Θ(m) time to compute π
• Matching: Θ(n) time, without backtracking

KMP simulates the behavior of a finite automaton without building it explicitly, making it efficient and widely used in practice.

Suffix Arrays and LCP Arrays

Suffix arrays store the starting indices of all suffixes of T in lexicographic order, enabling binary search for pattern P in O(m log n) time. When combined with the Longest Common Prefix (LCP) array, suffix arrays can solve advanced problems such as:

• Longest repeated substring
• Longest common substring between two texts

Suffix arrays are constructed in O(n log n) time using radix sort and rank-based merging. The LCP array is computed in Θ(n) time using inverse suffix arrays.

Choosing the Right Algorithm

Each string matching algorithm serves different needs:

• Naive: Simple, good for small inputs
• Rabin-Karp: Efficient for multiple patterns or approximate matching
• Finite Automaton: Fast matching with high preprocessing cost
• KMP: Efficient general-purpose exact matching
• Suffix Arrays: Best for advanced search tasks and repeated substring problems

Conclusion

String matching is a cornerstone of algorithm design with far-reaching applications from search engines to genome sequencing. Chapter 32 of Introduction to Algorithms offers a powerful toolkit of algorithms to handle pattern search tasks with precision and efficiency. Understanding the trade-offs among KMP, Rabin-Karp, automata, and suffix arrays allows you to choose the right approach for your problem space.

📺 Want a fast, visual summary? Watch the embedded lecture above and explore more chapters from Last Minute Lecture.

If you found this breakdown helpful, be sure to subscribe to Last Minute Lecture for more chapter-by-chapter textbook summaries and academic study guides.