Link

Description

子符串 $S$ 的前 $i$ 个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作 $num_i$，求出所有 $num_i$

Sol

重要性质：后缀同时又是它的前缀的数量 $f_i = f_{nxt_i - 1} + 1$

实际上跟 [Luogu3435 [POI2006]OKR-Periods of Words](https://www.luogu.com.cn/problem/P3435) 的性质很像，你可以知道，$nxt_i, nxt_{nxt_i},\dots$ 其实就是真前缀真后缀相等的长度，那每次递推往前求一下就得到了上面的式子。

注意判不相等，懒得讲了，这一部分我感觉网上的题解不是那么 naive

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int SIZE = 1e6 + 5;
const LL mod = 1e9 + 7;

int t, n;
int nxt[SIZE], f[SIZE];
char str[SIZE];

int main() {
    // freopen("code.in", "r", stdin);
    scanf("%d", &t);
    while (t --) {
        scanf("%s", str + 1);
        f[0] = 0, f[1] = 1, n = (int) strlen(str + 1);
        for (int i = 2, j = 0; i <= n; ++ i) {
            for ( ; j && str[i] != str[j + 1]; j = nxt[j]);
            if (str[i] == str[j + 1]) ++ j;
            nxt[i] = j, f[i] = f[j] + 1;
        }
        LL ans = 1ll;
        for (int i = 2, j = 0; i <= n; ++ i) {
            for ( ; j && str[i] != str[j + 1]; j = nxt[j]);
            if (str[i] == str[j + 1]) ++ j;
            for ( ; (j << 1) > i; j = nxt[j]);
            ans = (ans * (f[j] + 1ll) % mod) % mod;
        }
        printf("%lld\n", ans);
        for (int i = 0; i <= n; ++ i) f[i] = nxt[i] = 0;
    }
    return 0; 
}