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;
}