一个串是有限个小写字符的序列,特别的,一个空序列也可以是一个串. 一个串 是串 的前缀, 当且仅当存在串 , 使得 . 如果 并且 不是一个空串,那么我们说 是 的一个 前缀. 定义 是 的周期, 当且仅当 是 的一个 前缀并且 是 的前缀(不一定要是 前缀).
比如串 和 都是串 的周期. 串 的最大周期就是它最长的一个周期或者是一个空串(当 没有周期的时候), 比如说, 的最大周期是 . 串 的最大周期是空串. 给出一个串,求出它所有前缀的最大周期长度之和.
链接🔗
Luogu P3435
题解🔗
分析一下,可以发现我们要求的是所有前缀的最短的相同的前后缀,且还有长度的限制,不能超过字符串的一半。
这个可以联想到 ,所以我们思考如何在 的基础上维护这个事情。因为 在往回跳的话,是可以找到所有的相同的前后缀的。所以给定一个前缀,它沿 数组的转移是确定的,我们也就可以维护一个 ,就是最近能够跳到的长度,也就是相同的前后缀最短值,所以我们就可以 的根据 数组计算这个 数组,然后得到最后的答案。
代码🔗
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
| #include <cstdio>
using namespace std;
const int MAXN = 1100000;
char s[MAXN];
int n,nex[MAXN],near[MAXN];
void solve(){
int j;j = nex[0] = 0;
for(int i = 1;i<n;i++){
while(j > 0 && s[i] != s[j])
j = nex[j-1];
if(s[i]==s[j]) j++;
nex[i] = j;
}
j = 0;
long long ans = 0;
near[0] = 0;
for(int i = 1;i<n;i++){
int w = nex[i] - 1;
if(w >= 0)
near[i] = near[w] == -1?w:near[w];
else
near[i] = -1;
j = near[i]+1;
if(j > 0 && j <= (i+1)/2)
ans += (i+1)-j;
// printf("i:%d j:%d\n",i,j);
}
printf("%lld\n",ans);
}
void init(){
scanf("%d",&n);
scanf("%s",s);
}
int main(){
init();
solve();
return 0;
}
|