hdu3336Countthestring（思维可水过，KMP）

#include
#include<string.h>
#include
using namespace std;
int main()
{
int xin,t,i,j,n,ans,id,xiabiao[200010],shunxu;
char ch[200010];
scanf("%d",&t);
while(t--)
{

memset(xiabiao,0,sizeof(xiabiao));
scanf("%d",&n);
scanf("%s",ch);
id=0;shunxu=0;
ans=0;
for(j=0;j)
{
if(ch[j]==ch[shunxu])
xiabiao[id++]=j;
}
ans+=id;
ans=ans%10007;
do
{
shunxu++;
xin=0;
for(i=0;i)
{
if(xiabiao[i]+1<n)
{
if(ch[xiabiao[i]+1]==ch[shunxu])
{
xiabiao[xin++]=xiabiao[i]+1;
}
}
}
ans+=xin;
ans=ans%10007;
id=xin;
}while(shunxu1);
printf("%d\n",ans);
}
return 0;
}