本蒟蒻的第6篇题解——KMP

看这道题就是问p在s中出现了多少次，若按照暴力，就是两个指针，p[i]与s[j]一个一个比，如下

for(int i=1;i<=p.size();i++){
for(int j=1;j<=s.size();j++){
.......

用脚趾头想都知道，这样做肯定会TLE，那么，就可以用到KMP

我们可以去跳过某些没必要比对的；去直接比对需要的！接下来，要了解两个东西，前缀和后缀，现在假设这对 字符串p 的前后缀长度为 k 若这一对前后缀相同，则代表着下次移动，可以移动把前缀移到后缀处，例如aba 当 k 取1时，不难发现，前缀=a，后缀=a，则在ababa中，可以把指针i移动到第三个点，

ababa
aba
——>

ababa
  aba

可能有些难以理解，实在不懂就看看《信息学奥赛 一本通算法高效进阶（上册）》

这样做，不难发现，省去了模拟

ababa
 aba

节省了更多的时间！

以下为判断前后缀：

for(int i=2,j=0; i<=n; i++) {
    while(j&&p[j+1]!=p[i]) j=ne[j];判断是否相同，相同就把下次移动定到后缀最前。
    if(p[j+1]==p[i]) j++;//对齐
    ne[i]=j;
}

而后的代码是判断，这里与暴力基本一样的思路，就是一个个判断

for(int i=1,j=0; i<=m; i++) {
    while(j&&p[j+1]!=s[i]) j=ne[j];
    if(p[j+1]==s[i]) j++;
    if(j==n) {
        cout<<i-n<<' ';
        j=ne[j];
    }
}

这样整个题目便基本做出来了，如果发现有讲错的，欢迎指正！

完整代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char s[N],p[N];
int n,m,ne[N];
int main() {
    cin>>n>>p+1>>m>>s+1;
    for(int i=2,j=0; i<=n; i++) {
        while(j&&p[j+1]!=p[i]) j=ne[j];
        if(p[j+1]==p[i]) j++;
        ne[i]=j;
}
for(int i=1,j=0; i<=m; i++) {
    while(j&&p[j+1]!=s[i]) j=ne[j];
    if(p[j+1]==s[i]) j++;
    if(j==n) {
        cout<<i-n<<' ';
        j=ne[j];
        }
    }
    return 0;
}