String Matching Algorithms: Naive Search, Rabin-Karp, and Beyond

The String-Matching Problem

Given a Text T of length n and a Pattern P of length m (where m ≤ n), the String-Matching Problem asks for every position in T where P occurs as a substring. This operation underlies text editor search functions, DNA sequence matching in bioinformatics, and detecting plagiarism or code duplication.

The Naive String-Matching Algorithm

The most straightforward approach checks every possible starting position in the text, comparing the pattern character by character at each position.

NAIVE-STRING-MATCHER(T, P, n, m):
  for s = 0 to n - m:
      if P[1..m] == T[s+1..s+m]:
          print "Pattern occurs with shift" s

In the worst case, this algorithm's running time is O((n-m+1)m), since for each of the n-m+1 possible starting positions, up to m characters might need to be compared before a mismatch is found (or a full match confirmed).

A pathological worst case:
Text:    "aaaaaaaaaaaaaaaaaaaaaaaaaab"
Pattern: "aaaaaaaaab"

At almost every starting position, the algorithm must
compare nearly all m characters of the pattern before
finding the mismatch (or confirming the eventual match),
producing the full O(nm) worst-case behavior

Despite this poor worst case, the naive algorithm performs reasonably well in practice for typical text, where mismatches are usually found within the first few character comparisons, and its simplicity makes it a reasonable default for short patterns or infrequent searches.

The Rabin-Karp Algorithm: Using Hashing for Speed

The Rabin-Karp Algorithm takes a fundamentally different approach: instead of comparing characters directly at every position, it computes a numerical hash value, discussed earlier in this series regarding hash tables, for the pattern and for each length-m substring of the text, and only performs a full character comparison when the hash values match.

Computing Hash Values Efficiently with Rolling Hash

The key insight that makes this efficient is a Rolling Hash technique: rather than recomputing each substring's hash from scratch, which would take O(m) time per position and eliminate any speed advantage, the hash of the next substring can be computed in O(1) time from the hash of the current one.

Treating each substring as a number in base d
(where d is the size of the character alphabet):

hash(T[s+1..s+m]) = T[s+1]·d^(m-1) + T[s+2]·d^(m-2)
                     + ... + T[s+m]

To slide the window forward by one position:
hash(T[s+2..s+m+1]) =
  (hash(T[s+1..s+m]) - T[s+1]·d^(m-1)) · d + T[s+m+1]

This removes the leading character's contribution,
shifts the remaining digits, and adds the new
trailing character — all in O(1) time

In practice, this computation is done modulo a large prime number q, to keep the hash values within a manageable range and avoid overflow, while still preserving the property that equal substrings always produce equal hash values.

The Algorithm

RABIN-KARP-MATCHER(T, P, n, m, d, q):
  h = d^(m-1) mod q
  p = 0    // hash value of the pattern
  t0 = 0   // hash value of the first text window
  for i = 1 to m:
      p = (d·p + P[i]) mod q
      t0 = (d·t0 + T[i]) mod q
  for s = 0 to n - m:
      if p == ts:
          if P[1..m] == T[s+1..s+m]:    // verify to rule out false match
              print "Pattern occurs with shift" s
      if s < n - m:
          ts+1 = (d·(ts - T[s+1]·h) + T[s+m+1]) mod q

Why the Verification Step Is Essential

Because different substrings can occasionally produce the same hash value, an event called a Spurious Hit, the algorithm must always verify a full character-by-character match whenever the hash values agree, rather than trusting the hash match alone. Skipping this verification step would produce an incorrect algorithm that occasionally reports false matches.

Analyzing the Running Time

In the worst case, if every substring happens to produce the same hash value (an extraordinarily unlucky scenario, or one engineered by an adversary who knows the hash function), the algorithm degrades to the same O(nm) worst case as the naive algorithm, since every position would require full verification. However, if the hash function distributes values roughly uniformly (using probabilistic analysis similar in spirit to the techniques discussed earlier in this series), the expected number of spurious hits is small, giving an expected running time of O(n + m) — a dramatic improvement over the naive algorithm's worst case.

Why Rabin-Karp Is Especially Useful for Multiple-Pattern Search

A particular strength of Rabin-Karp emerges when searching for multiple patterns simultaneously, such as detecting several known plagiarized phrases at once: since the hash of each text window is computed only once regardless of how many patterns are being searched for, comparing that single hash against a precomputed set of pattern hashes is far more efficient than running an independent naive search once per pattern.

Comparing the Two Approaches

Naive Algorithm:
  - Worst case: O(nm)
  - Simple, no hash function needed
  - Fine for short patterns or infrequent searches

Rabin-Karp Algorithm:
  - Worst case: O(nm) (rare, only with poor hash function)
  - Expected case: O(n + m)
  - Well-suited to multiple-pattern search
  - Requires careful hash function design to avoid
    the pathological worst case in practice

Why String Matching Remains an Active, Practical Topic

Beyond the algorithms covered in this article, more advanced techniques such as the Knuth-Morris-Pratt algorithm (which achieves a guaranteed O(n + m) worst case by cleverly avoiding redundant comparisons using pattern-internal structure) and suffix trees (which preprocess the text itself to answer many pattern queries extremely quickly) push string matching performance even