- 题目链接： 模板_KMP字符串匹配
KMP算法
此算法为字符串匹配算法，此算法的优点在于，如果在匹配过程中失配，我们不需要从头开始，而是直接从某一特定位置开始，这样可以极大地节省时间复杂度，此算法的时间复杂度为θ(n)关于特定位置
我们来看一组样例
1
2模式串：abcab
文本串：abcacababcab首先，前四位按位匹配成功，遇到第五位不同，而这时，我们选择将abcab向右移三位，或者可以直接理解为移动到模式串中与失配字符相同的那一位。可以简单地理解为，我们将两个已经遍历过的模式串字符重合，导致我们可以不用一位一位地移动，而是根据相同的字符来实现快速移动。
即变为1
2模式串： abcabc
文本串：abcabdababcabc所以，对于模式串中的某一位置i，i的特定位置为j，满足j≤i 并且满足str1(i)=str1(j)str1(i)=str1(j) 并且在 j!=1j!=1 时理应满足 str1(1)str1(1)至str1(j-1)str1(j−1) 分别与 str(i-j+1)str(i−j+1)~str1(i-1)str1(i−1) 按位相等，我们把i的特殊位置用一个next数组来存
代码实现简述
我们首先要在模式串中找到每个位置的next，对于当前枚举到i，判断它前面的j是否等于i如果相等，把j记入next[i]，如果不相等，我们要缩小位置，令j=next[j]。然后模式串和文本串匹配，和之前找next方式基本一样，具体解释见代码。- 代码
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
using namespace std;
char a[Maxn], b[Maxn];
int next[Maxn];
int main() {
scanf("%s", a + 1);
scanf("%s", b + 1);
int len1 = strlen(a + 1);
int len2 = strlen(b + 1);
int j = 0;
for(int i = 2; i <= len2; i++) { //注意我们从2开始枚举，且j从0开始，所以i相当于i-1，换言说j相当于j+1
while(j > 0 && b[j + 1] != b[i]) //如果不匹配，则往前跳
j = next[j];
if(b[j + 1] == b[i]) //如果相等，要j++，因为j相当于j+1
j++;
next[i] = j;
}
j = 0;
for(int i = 1; i <= len1; i++) { //模式串和文本串匹配时从1开始
while(j > 0 && a[i] != b[j + 1]) //如果不匹配，则往前跳
j = next[j];
if(b[j + 1] == a[i]) //因为j从0开始，所以j要+1
j++;
if(j == len2) { //如果相等，输出位置
printf("%d\n", i - len2 + 1);
j = next[j];
}
}
for(int i = 1; i <= len2; i++)
printf("%d ", next[i]);
return 0;
}