对于一个目标串 t 和一个模式串 p，如何判断目标串中是否存在模式串？
例如：
若 t = "ababa"，p = "ab"，则目标串中存在模式串。
若 t = "ababa"，p = "ac"，则目标串中不存在模式串。
朴素思路
字符串匹配问题的朴素思路为遍历目标串 t 中的每个合法的位置，从该位置开始与模式串 p 依次进行比较，从而判断是否匹配，代码如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| bool match(const string &t, const string &p) {
int j = 0;
for (int i = 0; i < t.size() - p.size() + 1; i++) {
for (j = 0; j < p.size(); j++) {
if (t[i + j] != p[j]) {
break;
}
}
if (j == p.size()) {
return true;
}
}
return false;
}
|
不难看出，朴素思路的算法的时间复杂度为 O(t.size() * p.size())。当目标串和模式串长度较长时，算法的性能较差。
KMP
在朴素思路中，对于每个目标串中的每个位置都从模式串的起始位置进行字符串匹配，这样做实际上会引入一些不必要的比较。例如，对于下面这个例子。
1
2
3
4
5
6
7
8
9
10
11
| t = "ababac"，p = "abac"
朴素思路：
1. a b a b a c
a b a c
^失配
2. a b a b a c
a
^失配
3. a b a b a c
a b a c
^匹配成功
|
我们可以发现，在每次匹配失败时，我们总是将两个串上的指针回溯，而 KMP 算法则是尽量避免这种回溯，减少比较次数。在 KMP 算法中，对于每次失配，都会使目标串 t 上的指针不动，而令模式串 p 上的指针回溯。
那接下来的问题就是，KMP 中失配时，模式串指针回溯的位置至哪？对于上面例子中的模式串 p = "abac"，若匹配至 j = 3 时失配，那之前的字串 "aba" 是完全匹配的，且具有公共前后缀 "a"，那么模式串指针只需要回溯到 j = 1（此时 p[j = 0] = 'a' 已同目标串匹配）。模式串指针回溯问题也就转换成了求模式串的最长公共前后缀长度问题。
1
2
3
4
5
6
7
8
| t = "ababac"，p = "abac"
KMP：
1. a b a b a c
a b a c
^失配
2. a b a b a c
a b a c
^j 回溯
|
字符串 p 的最长公共前后缀长度使用数组 ne[] 存储，求 ne[] 可以使用递推的思路实现。对于 ne[j]，我们可以看 ne[j - 1] 得到子串的公共前后缀长度，然后比较字符 p[j] 和 p[ne[j - 1]] 是否相同，相同则 ne[j] = ne[j - 1] + 1，不相同则继续找公共前后缀的公共前后缀（公共前后缀缩短）。根据这个思路，我们可以得到求公共前后缀长度的算法及 KMP 字符串匹配算法，如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| vector<int> get_next(const string &p) {
vector<int> ne(p.size(), 0);
for (int i = 1, j = 0; i < p.size(); i++) {
while (j > 0 && p[i] != p[j]) j = ne[j - 1];
if (p[i] == p[j]) j++;
ne[i] = j;
}
return ne;
}
bool kmp(const string &t, const string &p) {
vector<int> ne = get_next(p);
for (int i = 0, j = 0; i < t.size(); i++) {
while (j > 0 && t[i] != p[j]) j = ne[j - 1];
if (t[i] == p[j]) j++;
if (j == p.size()) return true;
}
return false;
}
|
问题拓展
传统字符串匹配问题的拓展：对于目标串 t 和模式串 p，求出目标串中所有匹配模式串的索引。
例如：
若 t = "ababa"，p = "ab"，那么目标串所有匹配的索引为：{0, 2}。
若 t = "ababa"，p = "ac"，那么目标串所有匹配的索引为：{}。
拓展的字符串匹配问题需要在得到一次匹配后对该次匹配的结果进行记录并进行下一次匹配，拓展的朴素算法及 KMP 算法如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| vector<int> match(const string &t, const string &p) {
vector<int> res;
int j = 0;
for (int i = 0; i < t.size() - p.size() + 1; i++) {
for (j = 0; j < p.size(); j++) {
if (t[i + j] != p[j]) {
break;
}
}
if (j == p.size()) {
res.push_back(i);
}
}
return res;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| vector<int> get_next(const string &p) {
vector<int> ne(p.size(), 0);
for (int i = 1, j = 0; i < p.size(); i++) {
while (j > 0 && p[i] != p[j]) j = ne[j - 1];
if (p[i] == p[j]) j++;
ne[i] = j;
}
return ne;
}
vector<int> kmp(const string &t, const string &p) {
vector<int> ne = get_next(p);
vector<int> res;
for (int i = 0, j = 0; i < t.size(); i++) {
while (j > 0 && t[i] != p[j]) j = ne[j - 1];
if (t[i] == p[j]) j++;
if (j == p.size()) {
res.push_back(i - j + 1);
j = ne[j - 1];
}
}
return res;
}
|
