例题: luogu
知识点: 1.KMP 模板, 熟悉 KMP
2. 理解 KMP 过程: 失配时, 是从后缀转向前缀. 即失配时, 匹配串是从尾转到头继续匹配, 被匹配串不改变.
3. 注意字符数组的处理技巧: 输入时从 c[1] 开始输入, 求长度时也是求 strlen(c + 1).
- #include <bits/stdc++.h>
- using namespace std;
- int lena,lenb;
- char a[1000010],b[1000010];
- int kmp[1000010];
- int main()
- {
- scanf("%s",a + 1);
- scanf("%s",b + 1);
- lena = strlen(a + 1);
- lenb = strlen(b + 1);
- int j = 0;
- for(int i = 2;i <= lenb;i++)
- {
- while(j && b[j + 1] != b[i])j = kmp[j];
- if(b[j + 1] == b[i])j++;
- kmp[i] = j;
- }
- j = 0;
- for(int i = 1;i <= lena;i++)
- {
- while(j && b[j + 1] != a[i])j = kmp[j];
- if(b[j + 1] == a[i])j++;
- if(j == lenb)
- {
- printf("%d\n",i - lenb + 1);
- j = kmp[j];
- }
- }
- for(int i = 1;i <= lenb;i++)
- printf("%d",kmp[i]);
- return 0;
- }
KMP 记录
来源: http://www.bubuko.com/infodetail-2970072.html