831. KMP字符串

KMP思路：

求next数组，匹配字符串

1. next数组是求出每个p的下标能与前缀匹配的最长距离，求出那个点的坐标。求法就是和自己做匹配。
2. 匹配过程就是当遇到不匹配不相等时，p字符串最少后退多少才能继续匹配，这个最少后退的长度就是我们next所求出的下标。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=1e6+10;

int n,m;
char p[N],s[M];
int ne[N];

int main(){
    cin>>n>>p+1>>m>>s+1;
    //求next数组，也就是p和自己匹配
    for(int i=2,j=0;i<=n;i++){
        //j不为0并且匹配失败，p向右移动最少距离
        while(j&&p[j+1]!=p[i]) j=ne[j];
        //匹配成功，往下一个匹配
        if(p[j+1]==p[i]) j++;
        //当前位置i所能匹配的最长的下标为j
        ne[i]=j;
    }
    //p和s匹配
    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++;
        //如果p全部匹配成功
        if(j==n){
            printf("%d ",i-n);
            j=ne[j];//p向右移动最少距离
        }
    }
    cout<<endl;
    
    return 0;
}