http://acm.hdu.edu.cn/showproblem.php?pid=3336 题目
这是喵呜大神用KMP做的，46MS
#include <stdio.h>
#define MOD 10007
char b[200005];
int dp[200005];
int p[200005];
int n;
int Pre()
{
int s,i,j;
dp[0]=1;
j=-1;
p[0]=-1;
s=1;
for (i=1;i<n;i++)
{
while(j>=0 && b[j+1]!=b[i]) j=p[j];
if (b[j+1]==b[i]) j++;
if (j>=0) dp[i]=(dp[j]+1)%MOD;
else dp[i]=1;
p[i]=j;
s=(s+dp[i])%MOD;
}
return s;
}
int main()
{
int i,j,T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
scanf("%s",b);
printf("%d\n",Pre());
}
return 0;
}
思路：
1、首先确定这个字符串的首字母，然后从第二个开始搜起
当遇到和首字
符一样的时候，就从该字母开始后面的字符继续和这个字符串的首
字符
后续的字符进行比较，直到出现不一样为止，此时相同的字符个数就
加到总数上。
2、然后继续 从首字符下一个字符开始，
和1步骤差不多，就是这个字
符和前面的字符一起往后比较，遇到不
一样又重复这个步骤。。。
#include <stdio.h>
char str[200005];
int main()
{
int t,n,i,j,sum;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
sum=n;
sum%=10007;
scanf("%s",str);
for(i=1;i<n;i++)
{
if(str[i]==str[0])
{
for(j=i;j<n;j++)
{
if(str[j]!=str[j-i])
break;
}
sum+=j-i;
sum%=10007;
}
}
printf("%d/n",sum);
}
return 0;
}
