hdu3336 Count the string

 2 //从前向后扫，失配函数的位置就是一个前缀的位置减1
 3 //加起来就好了
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<algorithm>
 7 using namespace std;
 8 const int MAX = 200000;
 9 const int MOD = 10007;
10 char str[MAX];
11 int next[MAX],vis[MAX];
12 int main()
13 {
14     int cas,n;
15     scanf("%d",&cas);
16     while(cas--)
17     {
18         scanf("%d %s",&n,str);
19         next[0]=next[1]=0;
20         for(int i=1;i<n;i++)
21         {
22             int j=next[i];
23             while(j&&str[i]!=str[j]) j=next[j];
24             if(str[i]==str[j])
25             next[i+1]=j+1;
26             else next[i+1]=0;
27         }
28         int ans=0,cnt=0;
29         for(int i=0;i<n;i++)
30         {
31             if(next[i])
32             {
33             //    cnt++;
34                 ans=(ans+2)%MOD;
35             }
36             else
37             ans=(ans+1)%MOD;
38         }
39         if(next[n]) ans=(ans+1)%MOD;
40         printf("%d\n",(ans)%MOD);
41     }
42     return 0;