HDOJ - 1586 更新下KMP的模板...

    模板题...更新模板...

Program:

#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#define ll long long
#define oo 1000000000
using namespace std;
char s[2][1000005];
int _next[1000005];
int main()
{
int T,i,j,k,l0,l1,ans;
scanf("%d",&T);
while (T--)
{
scanf("%s%s",s[0]+1,s[1]+1);
l0=strlen(s[0]+1);
l1=strlen(s[1]+1);
memset(_next,0,sizeof(_next));
s[0][l0+1]='#';
for (i=2;i<=l0+1;i++)
{
k=_next[i-1];
while (k && s[0][k]!=s[0][i-1]) k=_next[k];
_next[i]=k+1;
}
k=ans=0;
for (i=1;i<=l1;i++)
{
k++;
while (k && s[0][k]!=s[1][i]) k=_next[k];
if (k==l0) ans++;
}
printf("%d\n",ans);
}
return 0;
}