🌐 中文 English
This article aims to explain how to implement the three core ideas of KMP Test link: https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/
What is KMP
KMP (Knuth-Morris-Pratt) is an efficient string search algorithm. Its core idea is to use partial match information to avoid repeated comparisons, thereby improving search efficiency.
The Three Core Ideas
First, look at the KMP code: (Test link: https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<string>
#include<vector>
using namespace std;
class Solution {
public:
vector<int> next;
int strStr(string haystack, string needle) {
int n = haystack.size();
int m = needle.size();
int x = 0, y = 0; // haystack, needle indices
vector<int> next(m);
// O(m)
build(next, needle, m);
// O(n)
while (x < n && y < m) {
if (haystack[x] == needle[y]) {
x++;
y++;
} else if (y == 0) {
x++;
} else {
y = next[y];
}
}
return y == m ? x - y : -1; // Starting index is x - y
}
// How to quickly generate the next array
void build(vector<int>& next, string& needle, int& m) {
if (m == 1) {
next[0] = -1;
return;
}
next[0] = -1;
next[1] = 0;
int i = 2, cn = 0;
// i(m) i - cn(m)
// up up
// unchanged up
// up up
while (i < m) {
if (needle[i - 1] == needle[cn]) { // Starting from index 2 - 1 in needle, initially needle[1] == needle[0] if equal
// Later, it's the case where it equals the previous value
next[i++] = ++cn; // Length can be at most one more than before, when equal to the value at the previous maximum position
} else if (cn > 0) { // cn > 0 : current position can still jump forward
cn = next[cn];
} else {
next[i++] = 0; // Jumped to the beginning and still not found
}
}
}
};
I will describe its core ideas based on this code.
Core Idea 1: next Index Assignment
The generation of the next array is the core part of the KMP algorithm. It records the length of the longest equal prefix and suffix for each position in the pattern string. Through this array, the KMP algorithm can quickly skip unnecessary comparisons when a match fails, thereby improving efficiency. Therefore, the values stored at different indices in the next array are carefully considered:
- next[i] = x: Corresponds to needle[i], where x is the length of the matching prefix and suffix of the string before needle[i], and the prefix and suffix cannot be the entire preceding string.
- next[0] = -1: The first character in next has no prefix or suffix, so a negative value is stored to indicate this.
- next[1] = 0: The prefix and suffix cannot be the entire string, so it is 0.
- The same logic applies for subsequent indices.
Core Idea 2: How the KMP Main Logic Uses next to Accelerate Matching
1
2
3
4
5
6
7
8
9
10
while (x < n && y < m) {
if (haystack[x] == needle[y]) {
x++;
y++;
} else if (y == 0) {
x++;
} else {
y = next[y];
}
}
Assume there is a substring aabaaf. We generate the next array for aabaaf:
- next[0] = -1
- next[1] = 0
- next[2] = 1
- next[3] = 0
- next[4] = 1
- next[5] = 2
We can easily observe:
When y = 4, the string before needle[4] is:aaba. needle[next[4] - 1] and needle[3] are the same. At this point, we can change comparing needle[4] with haystack[x] to comparing needle[next[4]] (needle[1]) with haystack[x]. This avoids comparing needle[0], thereby improving speed.
Core Idea 3: Using cn to Accelerate next Array Generation
1
2
3
4
5
6
7
8
9
10
while (i < m) {
if (needle[i - 1] == needle[cn]) { // Starting from index 2 - 1 in needle, initially needle[1] == needle[0] if equal
// Later, it's the case where it equals the previous value
next[i++] = ++cn; // Length can be at most one more than before, when equal to the value at the previous maximum position
} else if (cn > 0) { // cn > 0 : current position can still jump forward
cn = next[cn];
} else {
next[i++] = 0; // Jumped to the beginning and still not found
}
}
Why can cn accelerate the generation of the next array:
next[0] = -1, next[1] = 0 have already been initialized and are not included.
When needle[i - 1] and needle[cn] are equal, the value stored in next[i] is incremented by 1 compared to before, because when equal, both the prefix and suffix can be extended by 1 compared to before. When they are not equal, if cn is greater than 0, there may be a prefix matching the current suffix, allowing the suffix to be replaced with the prefix, thereby accelerating the generation of next.
FAQ
Why not initialize the array with next[0] = 0, next[1] = 1
next[0] = 0, next[1] = 1 is the standard version of KMP, while next[0] = -1, next[1] = 0 is the failure function version. It better handles next index relationships and can use cn to accelerate the construction of the next array, making it superior to the standard version.
