String Matching: Beyond the Naive Approach

Finding a pattern Pof lengthMwithin a textTof lengthNis a fundamental problem. While the naive approach takesO(N \cdot M), optimized algorithms achieve linear or sub-linear performance by exploiting the internal structure of the pattern.

1. Knuth-Morris-Pratt (KMP)

KMP avoids re-scanning characters by pre-processing the pattern to find the Longest Proper Prefix which is also a Suffix (LPS).

1.1 The LPS Array

For every positioniinP,LPS[i]stores the length of the longest proper prefix ofP[0 \dots i]that is also a suffix ofP[0 \dots i].

Example:P = \text{"ABABC"}* A: 0

• AB: 0
• ABA: 1 (A matches A)
• ABAB: 2 (AB matches AB)
• ABABC: 0

1.2 The Search Logic

When a mismatch occurs atP[j]andT[i], we do not reseti. Instead, we use the LPS array to "shift" the pattern:j = LPS[j-1]. This ensures we never back-track the text pointer, guaranteeing O(N+M) time complexity.

2. Boyer-Moore

Boyer-Moore is often faster than KMP in practice because it frequently skips large sections of the text. It scans the pattern from right to left.

2.1 The Bad Character Heuristic

When a mismatch occurs atT[i] = c:

• Ifcis not in the pattern, we shift the pattern pasti.
• Ifcis in the pattern, we shift the pattern to align the rightmost occurrence ofcinPwithT[i].

2.2 The Good Suffix Heuristic

If a suffix of the pattern has already matched before the mismatch, we shift the pattern to align that matched suffix with its next occurrence in the pattern.

2.3 Performance

• Average Case:O(N/M)(Sub-linear).
• Worst Case:O(N \cdot M)(thoughO(N+M)variants exist).

3. Rabin-Karp: Rolling Hashes

Rabin-Karp uses a Rolling Hash to find potential matches.

1. Compute hashH_Pof the pattern.
2. Compute hashH_Tof the current text window.
3. IfH_T = H_P, verify the match character-by-character.
4. UpdateH_TinO(1)time by subtracting the outgoing character and adding the incoming one.

Best For: Multiple pattern matching or searching in data streams.

Summary

Algorithm	Complexity (Avg)	Scan Direction	Key Mechanic
KMP	O(N+M)	Left-to-Right	LPS Array (Prefix/Suffix)
Boyer-Moore	O(N/M)	Right-to-Left	Bad Character / Good Suffix
Rabin-Karp	O(N+M)	Left-to-Right	Rolling Hash