831. KMP字符串
     题目链接

#include<iostream>
#include<string>
#include<vector>
using namespace std;

const int N=100000+10;

string T=" ",S=" ";
int tn,sn;

int nextval[N];
vector<int> vt;

void get_next(){
    int i=1,j=0;
    nextval[1]=0;
    while(i<=tn){
        if(j==0 || T[i]==T[j]){
            i++;
            j++;
            nextval[i]=j;
        }else{
            j=nextval[j];
        }
    }
}

void kmp(){
    get_next();
    int i=1,j=1;
        while(i<=sn){
            
            while(i<=sn && j<=tn){
                if(j==0 || S[i]==T[j]){
                    i++;
                    j++;
                }else{
                    j=nextval[j];
                }
            }
            if(j>tn){
                cout<<i-tn-1<<" ";
                j=nextval[j];
            }
        }
    
        
}

int main(){
    string ss;
    cin>>tn;
    cin>>ss;
    T+=ss;
    
    cin>>sn;
    cin>>ss;
    S+=ss;
    kmp();
    cout<<endl;
    // for(int i=1;i<=tn;++i){
    //     cout<<nextval[i]<<" ";
    // }
    
    
    return 0;
}