Pattern Searching
Pattern searching, also called string matching, is the problem of finding all positions in a text string T of length n where a pattern string P of length m...
Finding All Occurrences of a Pattern Within a Text String
Pattern searching, also called string matching, is the problem of finding all positions in a text string T of length n where a pattern string P of length m occurs as a contiguous subsequence. This problem appears in text editors (find and replace), bioinformatics (DNA sequence matching), network intrusion detection, and search engines.
The simplest approach is naive pattern matching: for each possible starting position i in T from 0 to n minus m, check whether the substring of T starting at i matches P character by character. If all m characters match, report position i. In the worst case, for example when T is all A's and P is all A's followed by a B, almost every starting position requires m comparisons before a mismatch is found. The worst-case time is O(n times m).
The naive algorithm performs redundant work because it ignores information gained from a failed match. When a mismatch occurs partway through comparing T with P, some prefix of P may match a suffix of the compared portion of T. Smarter algorithms exploit this observation to skip ahead in T rather than backing up to the position after the previous starting point.
Two foundational improvements are the Knuth-Morris-Pratt algorithm, which runs in O(n plus m), and the Boyer-Moore algorithm, which has O(n plus m) worst-case and is often much faster in practice because it can skip large portions of the text by scanning the pattern right to left and using mismatch information to jump ahead.
The Rabin-Karp algorithm takes a probabilistic approach using hashing: compute the hash of P and the hash of the current window of T of length m. If the hashes match, verify character by character. Rolling the window one position requires subtracting the leftmost character's contribution and adding the new rightmost character's contribution in O(1) using polynomial hashing, giving O(n plus m) average-case time.
Practical considerations: for single searches in short texts, the naive algorithm is often fast enough. For repeated searches with the same pattern or for very long texts, KMP or Boyer-Moore are preferred. For searching multiple patterns simultaneously, the Aho-Corasick algorithm builds a finite automaton over all patterns and matches all of them in a single O(n) text scan.
Worked example: find all occurrences of the pattern "ABAB" in the text "ABABCABAB". Naive matching finds matches at positions 0 and 5. KMP would reach the same result but skip redundant comparisons after the failed partial match at position 4, finding the result with fewer total character comparisons.
Interview tip: for pattern searching questions, start by implementing the naive approach and then discuss its weakness. Mention KMP or Rabin-Karp and explain the core insight of each. Knowing why KMP is O(n plus m) rather than O(n times m) demonstrates genuine understanding.