poj3461~KMP水水水題~

#include<iostream>
#include<string>
#include<fstream>
using namespace std;

int next[10005];
char t[10005],s[1000005];

void Getnext(char a[],int *next,int n)
{
  int i,j;
  j=-1;
  i=0;
  next[0]=-1;
  while(i<n)
    if(j==-1||a[i]==a[j])
    {
      i++;
      j++;
      next[i]=j;
    }
    else j=next[j];
}

int KMP(char S[],char T[]) //S是主串，T是子串
{
  int i=0,j=0,sum=0,lenT,lenS;
  lenT=strlen(T);
  lenS=strlen(S);
  Getnext(T,next,lenT); 
  while(i<lenS)
  {
    if(j==-1||S[i]==T[j])
    {
      i++;
      j++;
      if(j>=lenT)  //如果子串比對成功，sum++，後面的那個i繼續與
      {            //next【j】開始比對
        j=next[j];
        sum++;
      }
    }
    else j=next[j];
  }
  return sum;
}


int main()
{
  int i,j,x;
  cin>>x;
  while(x--)
  {
    scanf("%s%s",t,s);
    printf("%d\n",KMP(s,t));
  }
}