题目大意 : 在一个字符串中找出目标单词的个数

代码:

      #include<iostream>

      #include<cstdio>

      #include<cstdlib>

      #include<cstring>

      #include<queue>

      #include<algorithm>

      #include<cmath>

      #include<map>

      using namespace std;

      #define INF 0x7fffffff

      char t[1000010],w[10010];

      int next[10010];

      void getnext(int wlen){

	      int i,j;

	      next[0] = 0;

	      next[1] = 0;

	      for(i=1;i<wlen;i++){

		      j = next[i];

		      while(j && w[i] != w[j]) j = next[j];

		      if(w[i] == w[j]) next[i+1] = j+1 ;

		      else   next[i+1] = 0 ;

 	      }

      }

      int KMP(){

	      int i,j,tlen,wlen,cnt = 0;

	      tlen = strlen(t);

	      wlen = strlen(w);

	      j = 0;

	      getnext(wlen);

	      for(i=0;i<tlen;i++){

		      while(j && w[j] != t[i]) j = next[j];

		      if(w[j] == t[i]) j++;

		      if(j>=wlen)

		          cnt ++;

	      }

	      return cnt ;

      }

      int main(){

	      int  i,j,n,cnt;

	      cin >> n;

	      for(i=1;i<=n;i++){

		      scanf("%s%s",w,t);

		      printf("%d\n",KMP());

	      }  

	      return 0;

      }