Oulipo POJ - 3461

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

const int maxn=1000000+10;
int arrnext[maxn],lenT,lenW;
char W[maxn],T[maxn];

void creatnext(char *W)
{
    int i=0,j=-1;
    arrnext[0]=-1;
    lenT=strlen(T);
    while(i<lenT)
    {
        if(j==-1||W[i]==W[j])
        {
            i++;
            j++;
            arrnext[i]=j;
        }
        else j=arrnext[j];
    }
}

int KMP(char *W,char *T)
{
    int cnt=0,i=0,j=0;
    lenW=strlen(W);
    while(i<lenT)
    {
        if(j==-1||T[i]==W[j])
        {
            i++;
            j++;
        }
        else j=arrnext[j];
        if(j==lenW)
        {
            cnt++;
           // j=arrnext[j];
        }

    }
    return cnt;
}

int main()
{
    int kase;
    cin >> kase;
    while(kase--)
    {
        scanf("%s %s",W,T);
        creatnext(W);
        cout << KMP(W,T) << endl;
    }
    return 0;
}