kmp裸模版 poj 3461 博客分类： acm c++acm

#include <stdio.h>
#include <string.h>
using namespace std;
const int maxn = 1000000+10;
char s[maxn],t[maxn];
int next[maxn];
int m,n,k,l,i,T;
void get_next(char str[])
{
    memset(next,0,sizeof(next));
    next[1] = 0;
    int len = strlen(str+1),k=0;
    for(int i=2;i<=len;i++)
    {
        if(k>0&&str[i]!=str[k+1])
            k = next[k];
        if(str[i]==str[k+1])
            k++;
        next[i] = k;
    }
}
int kmp(char s[],char t[])
{
    get_next(s);
    int lent = strlen(t+1);
    int lens = strlen(s+1);
    int k=0,ans=0;
    for(int i=1;i<=lent;i++)
    {
        if(k>0&&t[i]!=s[k+1])
            k = next[k];
        if(t[i]==s[k+1])
            k++;
        if(k==lens)
        {
            ans++;
            k = next[k];
        }
    }
    return ans;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s+1);
        scanf("%s",t+1);
       printf("%d\n",kmp(s,t));

    }
    return 0;
}