http://uoj.ac/problem/5
题意：对于字符串S，求出每个前缀子串各有几个等于前缀且不相交的后缀。
就是要求在求解KMP的过程中能经过几次压缩，然后多了一个子串长度不能超过一半的要求。
但是显然不能对每个子串重新求一遍。可以发现KMP的next中每个串的后续是唯一的，也就是说再往后求就是重复计算了，所以考虑把算完的存下来，每次找到第一个符合条件的就直接用它的答案。
下面的程序里有两个指针j和k，要注意j不等于k，为了减少时间，重复利用了k，保证k一直都在串的前半截移动，虽然每次都从nxt[i]开始答案没错，但是会超时。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
int T;
char s[N];
int nxt[N], cnt[N];
int main() {
scanf("%d", &T);
while (T--) {
scanf("%s", s + 1);
int n = strlen(s + 1);
ll ans = 1ll;
memset(nxt, 0, sizeof(nxt));
memset(cnt, 0, sizeof(cnt));
cnt[1] = 1;
for (int i = 2, j = 0, k = 0; i <= n; i++) {
while (j&&s[i] != s[j + 1])j = nxt[j];
if (s[i] == s[j + 1])j++;
nxt[i] = j;
cnt[i] = cnt[j] + 1;
while (k&&s[i] != s[k + 1])k = nxt[k];
if (s[i] == s[k + 1])k++;
while ((k << 1) > i)k = nxt[k];
ans = ans * (cnt[k] + 1ll) % mod;
}
printf("%lld\n", ans);
}
return 0;
}
|
