题目链接
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4
5 inline int read()
6 {
7 int x=0,f=1;char ch=getchar();
8 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
9 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
10 return x*f;
11 }
12
13 /********************************************************************/
14
15 const int maxn = 1e6+6;
16 char s[maxn];
17 int Next[maxn];
18 int sum[maxn];
19
20 const int mod = 10007;
21
22 int main(){
23 int t; t = read();
24 while(t--){
25 int n; n = read();
26 scanf("%s", s+1);
27 //int len = strlen(s+1);
28 Next[1] = 0;;
29 int k = 0;
30 for(int i = 2;i <= n;i++){
31 while(k > 0 && s[k+1] != s[i]){
32 k = Next[k];
33 }
34 if(s[k+1] == s[i])
35 k++;
36 Next[i] = k;
37 }
38 int ans = 0;
39 memset(sum, 0, sizeof(sum));
40 for(int i = 1;i <= n;i++){
41 sum[i] = (sum[Next[i]] + 1)%mod;
42 ans = (ans + sum[i])%mod;
43 }
44 cout << ans << endl;
45 }
46 return 0;
47 }