KMP算法模板

#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
char s[100001],t[100001];
int next[100001];
int getnext(char* t,int *next)
{
    next[0]=-1;
    next[1]=0;
    int len=strlen(t);
    int i=1,j=0;
    while(i<len && j<len)
    {
        if(j==-1 || t[i]==t[j])next[++i]=++j;
        else j=next[j];
    }
    return 0;
}
int kmp(char *s,char *t)
{
    int i=0,j=0,len1=strlen(s),len2=strlen(t);
    while(i<len1 && j<len2)
    {
        if(j==-1 || s[i]==t[j])
        {
            i++;
            j++;
        }
        else j=next[j];
        if(j==len2)return i-len2;
    }
    return -1;
}
int main()
{
    freopen("kmp.in","r",stdin);
    freopen("kmp.out","w",stdout);
    scanf("%s",s);
    getchar();
    scanf("%s",t);
    getnext(t,next);
    printf("%d\n",kmp(s,t));
    fclose(stdin);
    fclose(stdout);
    return 0;
}