纯模板题：HDU1686
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define INF 1000005
int next[INF];
char a[INF],b[INF];
void getnext(char *str)
{
int j=0;
int len=strlen(str);
next[0]=0;
for(int i=1;i<len;i++)
{
while(j>0&&str[i]!=str[j])
j=next[j-1];
if(str[i]==str[j])
j++;
next[i]=j;
}
}
int kmp(char *str1,char *str2)
{
int len1=strlen(str1),len2=strlen(str2); //str1是待匹配串，str2是匹配串
int j=0,ans=0;
for(int i=0;i<len2;i++)
{
if(str1[j]!=str2[i]&&j>0)
j=next[j-1];
if(str1[j]==str2[i])
j++;
if(j==len1) //相等说明找到子串
ans++;
}
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s",a);
getnext(a);
scanf("%s",b);
int ans=kmp(a,b);
printf("%d\n",ans);
}
return 0;
}
next数组的运用（HDU3746）
#include<cstdio>
#include<cstring>
#define INF 1000005
int next[INF];
char inp[INF];
void getnext(char *a,int n)
{
int i=0,j=next[0]=-1;
while(i<n)
{
while(j!=-1&&inp[i]!=inp[j])
j=next[j];
i++;j++;
next[i]=j;
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s",inp);
int n=strlen(inp);
getnext(inp,n);
int ans=n-next[n];
if(n!=ans&&n%ans==0) printf("0\n");
else
{
ans=ans-next[n]%ans;
printf("%d\n",ans);
}
}
return 0;
}
