kmp模板

#include<stdio.h>
#include<string.h>
#define M 10005
#define N 1000005
int next[M];
char p[M],s[N];
int n, m;

void get_next()
{
    int i = 0, j = -1; //i为后指针,j为前指针
    next[0] = -1;
    //next[i]代表kmp不匹配时j跳回的位置，该位置前的位置是匹配的。
    /*
    当j==-1,p[-1]无意义，都跳回0
    当j>=0, 如果p[i]==p[j],next[i+1] = j+1;
            如果p[i]!=p[j],j=next[j],再比较
    */
    while(i<m)
    {
        if(j==-1 || p[i]==p[j])
            next[++i] = ++j;
        else
            j = next[j];
    }
}
int kmp()
{
    get_next();
    int i=0,j=0,num=0;
    while(i<n)
    {
        if(j==-1||s[i]==p[j])
        {
            i++;
            j++;
        }
        else
            j=next[j];
        if(j==m)
        {
            j = next[j];
            num++;
        }
    }
    return num;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(next,0,sizeof(next));
        scanf("%s%s",p,s);
        n = strlen(s);
        m = strlen(p);
        int ans=kmp();
        printf("%d
",ans);
    }
    return 0;
}