学步园

题目：http://poj.org/problem?id=3461
题目大意：给你两个串 p、t，让你求出 p 在 t 中出现的次数。
思路：kmp 模板题，没什么好说的。。 = =

代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

char p[11111],t[1111111];

int fail[11111];

void get_fail()
{
    int len = strlen(p);
    fail[0] = -1;
    int j = -1;
    for(int i = 1;i<len;i++)
    {
        while(j >= 0 && p[i] != p[j+1]) j = fail[j];
        if(p[i] == p[j+1]) j++;
        fail[i] = j;
    }
}

int kmp()
{
    get_fail();
    int len_p = strlen(p);
    int len_t = strlen(t);
    int cnt = 0;
    int j = -1;
    for(int i = 0;i<len_t;i++)
    {
        while(j >=0 && t[i] != p[j+1]) j = fail[j];
        if(t[i] == p[j+1]) j++;
        if(j == len_p - 1)
        {
            j = fail[j];
            cnt++;
        }
    }
    return cnt;
}

int main()
{
    int _;
    scanf("%d",&_);
    while(_--)
    {
        scanf("%s%s",p,t);
        printf("%d\n",kmp());
    }
    return 0;
}