前传：BF 算法
BF 算法即为暴力解法，一位一位向下匹配。
时间复杂度约为 。
KMP
KMP 算法的主要思想是利用部分匹配信息，避免重复匹配，提高字符串查找效率。
KMP 算法总时间复杂度是 ，匹配用时 。
为模式串长度， 为目标串长度。
KMP 算法第一步：构造 数组
思路
存储的是 模式串 的最长相同前后缀的长度。
例子如下：
1
2
| 字符串：`a b a b a`
kmp数组：0 0 1 2 3
|
aba，前后的 a 相同，故 。
ababa，前后的 aba 相同，故 。
代码理解
1
2
3
4
5
6
7
8
9
10
11
12
| kmp[1] = 0;
int len1 = strlen(s1 + 1);
int len2 = strlen(s2 + 1);
int j = 0;
for (int i = 2; i <= len2; i++)
{
while (j && s2[i] != s2[j + 1])
j = kmp[j];
if (s2[j + 1] == s2[i])
j++;
kmp[i] = j;
}
|
- 代表当前计算 时，前后缀匹配的长度。
- 逻辑：
- 若 ，说明 位置也能匹配前后缀相同， 并记录到 。
- 若 ，使用 回退，直到可以匹配或 。
KMP 算法匹配过程
前面说过了：
KMP 算法的主要思想是利用部分匹配信息，避免重复匹配。
我们求相同前后缀就是为了更好的跳跃。
如图所示，由于前后缀相同，我们可以直接跳跃至后缀部分，省去中间部分一位位匹配。
此部分代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
| j = 0;
for (int i = 1; i <= len1; i++)
{
while (j && s1[i] != s2[j + 1])
j = kmp[j];
if (s2[j + 1] == s1[i])
j++;
if (j == len2)
{
cout << i - len2 + 1 << "\n";
j = kmp[j];
}
}
|
P3375 AC 代码
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
| #include <bits/stdc++.h>
using namespace std;
char s1[1000005], s2[1000005];
int kmp[1000005];
int main()
{
cin >> s1 + 1;
cin >> s2 + 1;
kmp[1] = 0;
int len1 = strlen(s1 + 1);
int len2 = strlen(s2 + 1);
int j = 0;
for (int i = 2; i <= len2; i++)
{
while (j && s2[i] != s2[j + 1])
j = kmp[j];
if (s2[j + 1] == s2[i])
j++;
kmp[i] = j;
}
j = 0;
for (int i = 1; i <= len1; i++)
{
while (j && s1[i] != s2[j + 1])
j = kmp[j];
if (s2[j + 1] == s1[i])
j++;
if (j == len2)
{
cout << i - len2 + 1 << "\n";
j = kmp[j];
}
}
for (int i = 1; i <= len2; i++)
cout << kmp[i] << " ";
return 0;
}
|
后记
感谢能看到这里！
欢迎对本文提各种学术性的建议！
图较丑，比较糊，勿喷，谢谢。
