算法模板(八)字符串相关

KMP

#include<bits/stdc++.h>
#define maxn 1000006
using namespace std;
int next[maxn];
inline void getnext(char *p){
    next[0]=-1;
    int m=strlen(p);
    for(register int i=1;i<m;i++){      
        int j=next[i-1];        
        while(j>=0 && p[i]!=p[j+1])j=next[j];
        if(p[i]==p[j+1])j++;
        next[i]=j;
    }
}
inline int kmp(char *s,char *t){    
        int n=strlen(s),m=strlen(t);
    int j=-1;
    for(register inti=0;i<n;i++){
        while(j>=0 && s[i]!=t[j+1])j=next[j];
        if(s[i]==t[j+1]){
            j++;
        if(j+1==m)return i-m+1;
        }
    }
    return -1;
}
int main(){
    //freopen("1.txt","r",stdin);ios::sync_with_stdio(false);
    cin.tie(0);
    char s[maxn],t[maxn];
    cin>>s>>t;
    if(strlen(s)<strlen(t))swap(s,t);
    getnext(t);
    int now=kmp(s,t);
    while(now!=-1){
        cout<<now+1<<endl;
        for(register int i=0;i<=now;i++)s[i]=' ';
        now=kmp(s,t);
    }
    for(register int i=0;i<strlen(t);i++)cout<<next[i]+1<<" ";
    return 0;
}