KMP，额

容易理解不过我没用这个代码的讲解

非常清真的讲解

KMP中级题目汇总

hdu1711

//hdu1711 cww97
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1000007;
int Next[N],n,m,a[N],b[N];

void GetNext(int m){
    int i=0,j=-1;
    Next[0]=-1;
    while (i<m){
        if (j==-1||b[i]==b[j]){
            if (b[++i]!=b[++j])Next[i]=j;
            else Next[i]=Next[j];
        }else j=Next[j];
    }
}

int kmp(int n,int m){
    int i=0,j=0;
    GetNext(m);
    while (i<n&&j<m){
        if (j==-1||a[i]==b[j])i++,j++;
        else j=Next[j];
        if (!i&&!j)break;
    }
    if (j==m)return i-m+1;
    else return -1;
}

int main(){
    //freopen("fuck.in","r",stdin);
    int T;scanf("%d",&T);
    while (T--){
        scanf("%d%d",&n,&m);
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for (int i=0;i<n;i++)scanf("%d",&a[i]);
        for (int i=0;i<m;i++)scanf("%d",&b[i]);
        if (n<m)puts("-1");
        else printf("%d
",kmp(n,m));
    }
    return 0;
}

hdu2203

//hdu 2203 cww97
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=100007;
char st1[N],st2[N];
int Next[N];

void GetNext(char *a){
    int i=0,j=-1,len=strlen(a);
    Next[0]=-1;
    while (i<len){
        if (j==-1||a[i]==a[j]){
            if (a[++i]!=a[++j])Next[i]=j;
            else Next[i]=Next[j];
            //printf("%c:  %d
",a[i],next[i]);
        }else j=Next[j];
    }
}

bool kmp(char *a,char *b){
    int A=strlen(a),B=strlen(b),i=0,j=0;
    GetNext(b);
    while (i<A&&j<B){
        if (j==-1||a[i]==b[j])i=(i+1)%A,j++;
        else j=Next[j];
        if (!i&&!j)break;
    }
    return j==B;
}

int main(){
    //freopen("fuck.in","r",stdin);
    while (cin>>st1>>st2){
        int l1=strlen(st1),l2=strlen(st2);
        if (l1<l2)puts("no");
        else{
            if (kmp(st1,st2))puts("yes");
            else puts("no");
        }
    }
    return 0;
}

hdu3336

#include<cstdio>
#include<cstring>
using namespace std;
const int N=200007,P=10007;
int n;
char a[N];
int f[N],next[N];

void getNext(){
    int i=0,j=-1;
    next[0]=-1;
    while (i<n){
        if (j==-1||a[i]==a[j]){
            //if (a[++i]!=a[++j])next[i]=j;
            //else next[i]=next[j];
            next[++i]=++j;
            //printf("next[%d]=%d
",i,next[i]);
        }else j=next[j];
    }
}

int main(){
    //freopen("fuck.in","r",stdin);
    int T;
    scanf("%d",&T);
    while (T--){
        scanf("%d
",&n);
        for (int i=0;i<n;i++)scanf("%c",&a[i]);
        getNext();
        int ans=0;
        memset(f,0,sizeof(f));
        for (int i=1;i<=n;i++){
            //if (next[i]<=0)f[i]=1;
            //else 
                f[i]=(f[next[i]]+1)%P;
            //printf("f[%d]=%d
",i,f[i]);
            ans=(ans+f[i])%P;
        }
        printf("%d
",ans);
    }
    return 0;
} 

hdu5763,2016多校第四场
题解
这孩子居然暴力过了，数据有毒

/*令dp[i]表示到i结尾的字符串可以表示的不同含义数，那么考虑两种转移:
末尾不替换含义：dp[i - 1]
末尾替换含义：dp[i - |B|]  (A.substr(i - |B| + 1,|B|) = B)
那么对于末尾替换含义的转移，需要快速判断BB能不能和当前位置的后缀匹配，kmp或者hash判断即可。
复杂度:O(N)*/ 
//cww97
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=100007;
const int P=1000000007;
char a[N],b[N];
bool mat[N];
int next[N];
ll f[N];

void getNext(int m){
    int i=0,j=-1;
    next[0]=-1;
    while (i<m){
        if (j==-1||b[i]==b[j]){
            if (b[++i]!=b[++j])next[i]=j;
            else next[i]=next[j];
        }else j=next[j];
    }
}

void KMP(int n,int m){
    memset(mat,0,sizeof(mat));
    int i=0,j=0;
    getNext(m);
    while (i<n&&j<m){
        if (j==-1||a[i]==b[j])i++,j++;
        else j=next[j];
        if (!i&&!j)break;
        if (j==m){
            mat[i]=1;
            //printf("mat[%d]get
",i);
            j=next[j];
        }
    }
}

int main(){
    freopen("fuck.in","r",stdin);
    int T;
    scanf("%d
",&T);
    for (int cas=1;cas<=T;cas++){
        scanf("%s%s",a,b);
        int n=strlen(a);
        int m=strlen(b);
        KMP(n,m);
        memset(f,0,sizeof(f));
        f[0]=1;
        for (int i=1;i<=n+1;i++){
            if (mat[i])f[i]=(f[i-m]+f[i-1])%P;
            else f[i]=(f[i-1])%P;
            //printf("f[%d]=%d
",i,f[i]);
        }
        printf("Case #%d: %I64d
",cas,f[n]%P);
    }
    return 0;
}