POJ 3461 KMP

      就是在KMP的时候当匹配到比配串的最后一位的时候sum ++就行了，这里提示一下，这个题目说的是可以叠加，如果不可以重叠的，比如aaa aaaaa 输出的应该是1，为为子串不到6个，这样的我们在KMP匹配到匹配串最后一个的时候要把i++ ,j = 0,这样就可以了。

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

int next[10005];
char a[1000005] ,b[10005];

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];
   }
}

int KMP(int n ,int m)
{
    int sum = 0,i ,j;
    for(i = j = 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);
       get_next(m);
       printf("%d\n" ,KMP(n ,m));
    }
    return 0;
}