String Pattern Matching
String pattern matching finds occurrences of a pattern in a text. Classic algorithms: naive (BF), KMP, etc.
String pattern matching demo
This placeholder can be extended with an animation of the matching process of algorithms such as KMP.
- Aligning the text and the pattern
- next array jump demo
- Match / mismatch process
Naive (Brute Force)
- Align pattern and text, compare sequentially
- Time , text length, pattern length
KMP
- Uses prefix table (next array) to avoid re-checking
- Time
- Text editor find/replace
- DNA sequence analysis
- Search/retrieval, data mining
Naive:
for i = 0 to m-n:
for j = 0 to n-1:
if S[i+j] != P[j]:
break
if j == n:
return i // match
return -1
KMP (simplified):
build next array
i = 0, j = 0
while i < m:
if S[i] == P[j]:
i++, j++
if j == n: return i-n // match
else if j > 0:
j = next[j-1]
else:
i++
return -1
The next array is the heart of KMP. When the pattern prefix mismatches at , the index has to fall back to the position next[j]. next[j] is the length of the longest equal prefix-and-suffix of .
Steps to build it
next[0] = -1— a mismatch on the very first character means the text pointer advances.- Recurse for
next[j]: letk = next[j-1]; ifP[j-1] == P[k]thennext[j] = k+1, otherwise setk = next[k]and keep falling back.
Example: the pattern “abaabc”
| j | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| P[j] | a | b | a | a | b | c |
| next[j] | -1 | 0 | 0 | 1 | 1 | 2 |
Working through it:
next[0] = -1j=1: the substringahas no equal prefix and suffix, sonext[1] = 0j=2: the substringabhas longest equal prefix and suffix of length 0, sonext[2] = 0j=3: the substringabahas longest equal prefix and suffixa, length 1, sonext[3] = 1j=4: the substringabaahas longest equal prefix and suffixa, length 1, sonext[4] = 1j=5: the substringabaabhas longest equal prefix and suffixab, length 2, sonext[5] = 2
Why it works: on a mismatch at P[j], the pattern pointer falls back to next[j] and comparison continues, while the text pointer i never moves backwards. That single asymmetry is what turns the worst case from into .
Implementation
// Build the next array for pattern P of length n.
void GetNext(char P[], int next[], int n) {
next[0] = -1;
int i = 0, k = -1;
while (i < n - 1) {
if (k == -1 || P[i] == P[k]) {
i++;
k++;
next[i] = k;
} else {
k = next[k]; // fall back to a shorter border
}
}
}
// KMP search: S is the text (length m), P is the pattern (length n).
int KMP(char S[], char P[], int next[]) {
int i = 0, j = 0;
while (i < (int)strlen(S) && j < (int)strlen(P)) {
if (j == -1 || S[i] == P[j]) {
i++;
j++;
} else {
j = next[j]; // the pattern falls back, the text does not
}
}
if (j == (int)strlen(P))
return i - j; // match: return the start position
return -1; // no match
}
The k = next[k] line in GetNext is the same idea as j = next[j] in the search, applied to the pattern itself. Read together, the two routines say: when a comparison fails, do not start over — fall back to the longest border that could still lead to a match.
- Naive:
- KMP:
Exercise 1
Explain KMP idea and its advantage.
Approach: The next array avoids repeated comparisons.
Steps:
- Use the next array to skip the prefix that has already been matched
- Time
Answer: The next array keeps the text pointer from backtracking, which improves the efficiency.
Exercise 2
Time complexity of naive vs KMP?
Approach: Compare the characters directly.
Steps:
- Naive matching
- KMP
Answer: Naive matching is while KMP is .
2022·408
How does KMP avoid backtracking the text pointer?
Approach: Jumping along the next array.
Steps:
- The text pointer does not backtrack when a match fails
- The pattern pointer jumps according to the next array
Answer: The pattern jumps along the next array, so the text never backtracks.
