POJ 3461

神奇的KMP

#include <stdio.h>
#include <string.h>
#define XSIZE 10001
int preKmp(char *x, int kmpNext[]) {
   int i, j;
   for(i=0,j=kmpNext[0]=-1;x[i];) {
       while (j>-1 && x[i]!=x[j])
           j = kmpNext[j];
       ++i;
       ++j;
       if (x[i] == x[j])
           kmpNext[i] = kmpNext[j];
       else
           kmpNext[i] = j;
   }
   return i;
}

int KMP(char *x, char *y){
   int i, j, kmpNext[XSIZE];
   int nc=0;
   /* Preprocessing */
   int m=preKmp(x, kmpNext);
   /* Searching */
   for(i=j=0;y[j];){
       while (i>-1 && x[i]!=y[j])
           i = kmpNext[i];
       ++i;
       ++j;
       if(i>=m){
           ++nc;
           i=kmpNext[i];
       }
   }
   return nc;
}

int main() {
   int N;
   char W[XSIZE],T[1000001];
   for(scanf("%d",&N);N;--N){
       scanf("%s%s",W,T);
       printf("%d\n",KMP(W,T));
   }
   return 0;
}