题目传送门
做法：
这题里面的num数组看上去非常玄乎，实际上仍然离不开kmp。不过一定注意num是指符合条件的字符串的个数，而不是像kmp一样记录最长的字符串的长度。做法其实十分简单。在kmp的时候记录cnt数组，即满足既是前缀，又是后缀的字符串的个数，1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
注意ans要开long long。
### 代码：
```C++
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1000005;
int n;
char s[N];
int num[N],nxt[N],cnt[N];
const int p = 1e9 + 7;
int main()
{
scanf("%d", &n);
//cout<<p<<endl;
for (int i = 1; i <= n; i++)
{
memset(nxt, 0, sizeof nxt);
memset(num, 0, sizeof num);
memset(cnt, 0, sizeof cnt);
//char s[N];
scanf("%s",s);
int len = strlen(s);
nxt[1] = 0;
cnt[1] = 1;
int k = 0;
for (int j = 1; j < len; j++)
{
while (k && s[j] != s[k]) k = nxt[k];
if (s[j] == s[k]) nxt[j + 1] = ++k;
cnt[j + 1] = cnt[k] + 1;
}
long long res = 1;
k = 0;
for (int j = 1; j < len; j++)
{
while (k && s[j] != s[k]) k = nxt[k];
//if(k == 0) continue;
if (s[k] == s[j]) k++;
while((k * 2) > j + 1 ) k = nxt[k];
// cout << cnt[k] << " ";
res = (p + res * (cnt[k] + 1)) % p;
}
printf("%lld\n",res);
}
return 0;
}