String and Pattern Matching Algorithms
Open in the Padhaiko app4.1 String matching fundamentals
Given a text of length and a pattern of length over a finite alphabet , the string matching problem seeks all valid shifts such that:
Prefixes, Suffixes, and Borders
Let be strings over alphabet :
- is a prefix of () if for some .
- is a suffix of () if for some .
- A string is a proper border of if is both a proper prefix and a proper suffix of ().
Naive String Matching and Finite-Automaton Matcher
- Naive (Brute-Force) Algorithm: Checks every shift by comparing against character by character.
- Worst-case time: (e.g., , ).
- Preprocessing time: ; Extra space: .
- Finite Automaton String Matcher: Precomputes a transition function for states (longest prefix of that is a suffix of ). Scanning takes time with zero backtracking, at a preprocessing cost of (or naively).
| Algorithm | Preprocessing Time | Matching Time (Worst-Case) | Extra Space | Key Mechanism |
|---|---|---|---|---|
| Naive | Slide by and re-check from start | |||
| Finite Automaton | Full transition table | |||
| Knuth–Morris–Pratt (KMP) | Prefix / failure function (LPS) | |||
| Rabin–Karp | worst / expected | Rolling hash modulo prime | ||
| Boyer–Moore | worst / sublinear typical | Right-to-left scan + bad-character & good-suffix |
4.2 Knuth-Morris-Pratt algorithm
The Knuth–Morris–Pratt (KMP) algorithm eliminates redundant character re-comparisons after a mismatch by precomputing the prefix function (also called the longest proper prefix-suffix (LPS) or failure array) of the pattern alone.
KMP Prefix Function (LPS Array)
For each , is the length of the longest proper prefix of that is also a suffix of :
(By convention because a -character string has no non-empty proper prefix.)
Computing and Searching in Time
- Preprocessing
COMPUTE-PREFIX-FUNCTION(P): Maintain current matched prefix length for to . While and , fall back via . If , increment , and set . - Matching: Scan left to right while tracking matched pattern length . On mismatch (), set without ever decrementing .
- Amortized Complexity Proof: Each
whilefallback strictly decreases (or ) by at least , while (or ) increases by at most per outer-loop step ( or times) and never becomes negative. Therefore total fallbacks during preprocessing and during matching, giving preprocessing and matching.
def compute_lps(pattern):
m = len(pattern)
lps = [0] * m
k = 0
for i in range(1, m):
while k > 0 and pattern[k] != pattern[i]:
k = lps[k - 1]
if pattern[k] == pattern[i]:
k += 1
lps[i] = k
return lps
def kmp_search(text, pattern):
n, m = len(text), len(pattern)
if m == 0:
return []
lps = compute_lps(pattern)
matches = []
q = 0
for i in range(n):
while q > 0 and pattern[q] != text[i]:
q = lps[q - 1]
if pattern[q] == text[i]:
q += 1
if q == m:
matches.append(i - m + 1)
q = lps[q - 1]
return matches1
Construct the KMP prefix function (0-indexed LPS array) for the pattern (length ), and trace KMP matching against the text .
Compute the prefix function for :
- (
A): . - (
B): . - (
A): (A). - (
B): (AB). - (
A): (ABA). - (
C): ; ; . - (
A): .
Thus .
Trace KMP on (indices ):
- (
ABABA): advances . - ( vs. ): mismatch! Fallback . Now compare with : match! So .
- ( vs. ): match .
- ( vs. ): match .
- ( vs. ): match ! Record match at shift , and set .
- ( vs. ): match . End of text.
The KMP prefix array for ABABACA is , and KMP finds the single occurrence at shift ().
4.3 Rabin-Karp algorithm
The Rabin–Karp algorithm uses rolling hashing to compare the numerical hash of against the hash of every length- substring window in amortized time per shift, making it particularly effective for multi-pattern matching and plagiarism detection.
Polynomial Rolling Hash Modulo Prime q
Treating characters as digits in radix modulo a prime , the hash of and window are:
Given , the next window hash is updated in arithmetic operations:
- Spurious Hits: When , and might differ due to a hash collision (spurious hit), so Rabin–Karp performs an explicit character verification whenever .
- Complexity: Expected time is when is large enough that spurious hits are rare (expected hits); worst-case time is if every shift triggers a spurious hit.
2
In decimal () modulo prime , search for pattern () in text using the Rabin–Karp rolling hash over the first shifts (). Identify all hash hits, distinguish spurious hits from valid matches, and show the rolling update from to .
Precompute and pattern hash :
Initial window :
Compute rolling hashes from to :
- (
359): . - (
590): . - (
902): . - (
023): . - (
231): . - (
314): ! Character check confirms (valid match at ).
(Note: if the window were 614, , whereas 015 gives , which would be a spurious hit.)
With and , rolling hashes are , producing zero spurious hits on and one valid match at (314).
4.4 Boyer-Moore algorithm
The Boyer–Moore algorithm scans the pattern from right to left ( down to ) at each shift , allowing large jumps past mismatched characters and often achieving sublinear average time on natural-language text.
Two Shift Heuristics
When a mismatch occurs at :
- Bad-Character Rule: Locate the rightmost occurrence of character in at index (or if does not appear in ). Shift right by so that the mismatched text character aligns with (or jumps completely past if ).
- Good-Suffix Rule: Let be the suffix of that did match before the mismatch at . Shift right to:
- align the rightmost earlier occurrence of in preceded by a character , or
- if no such occurrence exists, align the longest prefix of that matches a suffix of (else shift by ).
At every mismatch, Boyer–Moore takes the maximum of the two shifts:
- Boyer–Moore–Horspool Variant: Uses only a simplified bad-character shift keyed on the last character of the window , giving fast practical performance with preprocessing.
- Complexity: Worst-case in naive form ( with Galil's rule); best/typical case when mismatches occur immediately at for characters absent from .
4.5 Suffix arrays and trees
When a fixed large text (such as a genome or document corpus) is queried repeatedly for arbitrary patterns , preprocessing rather than into a suffix tree or suffix array answers pattern queries in time independent of .
Suffix Tree, Suffix Array, and LCP Array
Let be a string of length terminated by a unique sentinel smaller than every character in :
- Suffix Tree: A compressed trie containing all suffixes (), where edges are labeled by substrings (stored as
(start, end)index pairs) and every internal non-root node has at least two children. - Suffix Array (): An integer array storing the starting indices of all suffixes of sorted in lexicographical order.
- LCP Array: Stores between adjacent sorted suffixes and ().
| Aspect | Suffix Tree | Suffix Array |
|---|---|---|
| Construction Time | (Ukkonen's algorithm) | (prefix doubling) or (SA-IS / DC3) |
| Memory Footprint | High ( bytes per char) | Compact ( bytes per char) |
| Pattern Search ( of len ) | or | binary search, or using LCP |
| Core Applications | Longest repeated substring, LCS of two strings, DNA motif search | Full-text indexing, Burrows–Wheeler / FM-index compression |
Key Operations on Suffix Trees and Arrays
- Exact Pattern Matching: Every occurrence of is a prefix of some suffix of , so occurrences form a single subtree in a suffix tree or a contiguous range in found via binary search.
- Number of Distinct Substrings: Every substring of length is a prefix of some suffix; summing non-redundant suffix lengths using the LCP array gives:
3
For the string (, 0-indexed without sentinel or treating indices directly):
- Construct the Suffix Array and the LCP array .
- Using and , compute the exact number of distinct non-empty substrings of
banana.
List and sort all suffixes of banana:
- :
banana - :
anana - :
nana - :
ana - :
na - :
a
Sorting lexicographically gives:
- Index :
a - Index :
ana - Index :
anana - Index :
banana - Index :
na - Index :
nana
So .
Compute the LCP array between adjacent sorted suffixes:
- (
a) - (
ana) - (
na)
So .
Count distinct non-empty substrings:
For banana, , , and there are distinct non-empty substrings.
Exercises
Practice Exercises — String and Pattern Matching Algorithms
Compare the Naive, KMP, and Rabin–Karp string matching algorithms on preprocessing time, worst-case matching time, and space complexity. Give a concrete example of text (length ) and pattern (length ) that triggers the worst-case comparison count in the Naive algorithm, and count the exact number of character comparisons made.
Comparison: Naive takes preprocessing, worst-case matching, and space. KMP takes preprocessing, worst-case matching, and space. Rabin–Karp takes preprocessing, expected ( worst-case) matching, and space.
Worst-case Naive example (): Take ( As) and (length ). There are valid shifts (). At every shift, the first two comparisons (A == A, A == A) succeed and the third comparison (A != B) fails, performing comparisons per shift.
KMP guarantees worst-case time using space, whereas Naive and Rabin–Karp can degrade to . For and , Naive makes character comparisons.
Compute the KMP prefix function (0-indexed LPS array) for the pattern (). Show how avoids redundant comparisons if a mismatch occurs at while matching against a text character 'C'.
Compute for :
- (
A): - (
A): (A) - (
B): - (
A): (A) - (
A): (AA) - (
C): ; - (
A): (A) - (
A): (AA) - (
B): (AAB) - (
A): (AABA) - (
A): (AABAA)
So .
Mismatch fallback at against 'C': If mismatches text character 'C', KMP sets (reusing the AABA prefix without backing up the text index), tests , falls back to , tests , falls back to , and then advances past 'C'.
The 0-indexed prefix array is ; on mismatch at , chains with zero text backtracking.
Explain what a spurious hit is in the Rabin–Karp algorithm and how it affects worst-case complexity. With radix , prime , and pattern () against window : compute for 231, compute for 315 using the rolling hash update, and check whether 011 would cause a spurious hit against modulo .
Spurious hits and complexity: A spurious hit occurs when the window's modular hash equals the pattern's hash , yet the actual substrings differ (). Each hit requires an character verification; if an adversarial input causes spurious hits, total time degrades to .
Rolling hash update and spurious-hit check ():
- .
- Pattern hash: (since ).
- for
231: . - Rolling update to for
315:
- For
011(), no hit occurs; by contrast,007gives , which is a spurious hit because007 != 315.
A spurious hit is a hash match () between unequal strings, degrading Rabin–Karp to in the worst case. Here , , (valid match), and 011 hashes to (not a spurious hit, whereas 007 would be).
Describe the bad-character and good-suffix heuristics of the Boyer–Moore algorithm. Search for pattern () inside (focus on the first shift ): show the right-to-left comparison at , identify the mismatch, and compute the shift distance using the bad-character rule.
Bad-character and good-suffix rules: Boyer–Moore aligns at shift and compares from down to . On mismatch , the bad-character rule shifts by to align with its rightmost occurrence in (or jump past if ). The good-suffix rule shifts the matched suffix to its next valid occurrence (or longest matching prefix) in ; the algorithm advances by the larger of the two shifts.
First alignment ( vs. ):
- Compare : vs. immediate mismatch!
- Mismatched text character is at .
- In (indices :
G:0, C:1, A:2, G:3, A:4, G:5, A:6, G:7), the rightmost occurrence of'A'is at . - Bad-character shift: (shifting right by aligns with ).
Boyer–Moore compares right-to-left and takes . At , mismatches ; since , the bad-character rule shifts right by position.
Compare Suffix Trees and Suffix Arrays in space usage and pattern-search complexity. Construct the Suffix Array and LCP array for (), and use them to count the exact number of distinct non-empty substrings of ababa.
Suffix Tree vs. Suffix Array: A suffix tree allows (or ) search directly along edges, but pointer-heavy nodes consume the text size. A suffix array stores only integer offsets ( bytes/char), searching in (or with an LCP array).
Construct , , and count distinct substrings for : Suffixes: , , , , . Sorted order:
- :
a() - :
aba(, shareda) - :
ababa(, sharedaba) - :
ba() - :
baba(, sharedba)
Using the LCP sum formula:
(Direct check: a, b, ab, ba, aba, bab, abab, baba, ababa — substrings.)
Suffix arrays trade (or ) search for a fraction of a suffix tree's memory. For ababa, , , and there are distinct non-empty substrings.