字符串

KMP模板

P3375【模板】KMP

int nxt[N];
string s,p;
void solve(){
    cin>>s>>p;
    int ls=s.size(),lp=p.size();    
    s=" "+s;
    p=" "+p;
    for(int i=2,j=0;i<=lp;i++){
        while(j&&p[i]!=p[j+1])j=nxt[j];
        if(p[i]==p[j+1])j++;
        nxt[i]=j;
    }
    for(int i=1,j=0;i<=ls;i++){
        while(j&&s[i]!=p[j+1])j=nxt[j];
        if(s[i]==p[j+1])j++;
        if(j==lp){
            cout<<i-lp+1<<"\n";
            j=nxt[j];
        }
    }
    for(int i=1;i<=lp;i++)cout<<nxt[i]<<" ";
}

P4391无线传输

求最小循环串,即n-nxt[n]

int nxt[N];
string p;
void solve(){
    int n;
    cin>>n;
    cin>>p;
    int lp=p.size();    
    p=" "+p;
    int mn=1e9;
    for(int i=2,j=0;i<=lp;i++){
        while(j&&p[i]!=p[j+1])j=nxt[j];
        if(p[i]==p[j+1])j++;
        nxt[i]=j;
        mn=min(mn,i-nxt[i]);
    }
    //for(int i=1;i<=n;i++)cout<<nxt[i]<<" ";
    cout<<n-nxt[n];
}