hdu1686 最大匹配次数 KMP

题意：
     给你两个串，问你串a在串b中出现了多少次。


思路：

      直接匹配，KMP时匹配到匹配串的最后一个的时候不用跳出，直接匹配就行了，最后一个'/0'不会和目标串匹配，所以经过next[l2]就直接自动找到该去的位置了，怎么说呢，今天刚学的KMP，给我的感觉就是"记忆化搜索"。

#include<stdio.h>
#include<string.h>

char a[1100000] ,b[11000];
int next[11000];

void get_next(int m)
{
   int j ,k;
   j = 0 ,k = -1;
   next[0] = -1;
   while(j < m)
   {
      if(k == -1 || b[j] == b[k])
      next[++j] = ++ k;
      else
      k = next[k];
   }
   return ;
}

int KMP(int n ,int m)
{
   int sum = 0;
   int i ,j;
   for(j = i = 0 ;i < n ;)
   {
      if(a[i] == b[j])
      {
         if(j == m - 1)
         sum ++;
         i ++ ,j ++;
      }
      else
      {
         j = next[j];
         if(j == -1)
         {
            j = 0;
            i ++;
         }
      }
   }
   return sum;
}

int main ()
{
   int t ,n ,m;
   scanf("%d" ,&t);
   while(t--)
   {
      scanf("%s %s" ,b ,a);
      n = strlen(a);
      m = strlen(b);
      if(m > n) puts("0");
      else
      {
         get_next(m);
         printf("%d
" ,KMP(n ,m));
      }
   }
   return 0;
}