KMP字符串

#include <iostream>
using namespace std;

const int N = 1000010;
int ne[N];
string s,p;

int main(){
    int a,b;
    cin>>a>>p>>b>>s;
    int i=1,j=0;
    while(i<p.size()){
        // ne[i]代表从0-i之间最大相同前后缀的长度 即 前缀后的第一个下标
        // 如果从j处不匹配了，说明0-(j-1)是匹配的，回溯0-(j-1)前缀即可
        if(p[i]==p[j]){
            ne[i]=j+1;
            i++;
            j++;
        }else{
            if(j==0)i++;
            else j=ne[j-1];
        }
    }
    i=0,j=0;
    while(i<s.size()){
        // ne[i]代表从0-i之间最大相同前后缀的长度 即 前缀后的第一个下标
        if(s[i]==p[j]){
            i++;
            j++;
        }else{
            if(j==0)i++;
            else j=ne[j-1];
        }
        if(j==p.size()){
            //success
            printf("%d ",i-j);
            j=ne[j-1];
        }
    }
    return 0;
}