POJ 3461 Oulipo

POJ_3461

    今天开始学KMP啦，从gestapolur那里听说到Matrix67写的KMP通俗易懂，于是便去那里学了。http://www.matrix67.com/blog/archives/115

#include<stdio.h>
#include<string.h>
#define MAXW 10010
#define MAXT 1000010
int N, P[MAXW];
char word[MAXW], txt[MAXT];
void prepare()
{
    int i, j;
    P[1] = j = 0;
    for(i = 2; word[i]; i ++)
    {
        while(j && word[j + 1] != word[i])
                j = P[j];
        if(word[j + 1] == word[i])
            ++ j;
        P[i] = j;
    }
}
void solve()
{
    int i, j, k, len, cnt = 0;
    scanf("%s%s", word + 1, txt + 1);
    prepare();
    j = 0;
    len = strlen(word + 1);
    for(i = 1; txt[i]; i ++)
    {
        while(j && word[j + 1] != txt[i])
            j = P[j];
        if(word[j + 1] == txt[i])
            ++ j;
        if(j == len)
        {
            ++ cnt;
            j = P[j];
        }
    }
    printf("%d\n", cnt);
}
int main()
{
    int i;
    while(scanf("%d", &N) == 1)
    {
        for(i = 0; i < N; i ++)
            solve();
    }
    return 0;
}