「POI2006」Periods of Words-KMP

一个串是有限个小写字符的序列,特别的,一个空序列也可以是一个串. 一个串 $P$ 是串 $A$ 的前缀, 当且仅当存在串 $B$ , 使得 $A = PB$. 如果 $P \neq A$ 并且 $P$ 不是一个空串,那么我们说 $P$ 是 $A$ 的一个 $proper$ 前缀. 定义 $Q$ 是 $A$ 的周期, 当且仅当 $Q$ 是 $A$ 的一个 $proper$ 前缀并且 $A$ 是 $QQ$ 的前缀(不一定要是 $proper$ 前缀).

比如串 $abab$ 和 $ababab$ 都是串 $abababa$ 的周期. 串 $A$ 的最大周期就是它最长的一个周期或者是一个空串(当 $A$ 没有周期的时候), 比如说, $ababab$ 的最大周期是 $abab$ . 串 $abc$ 的最大周期是空串. 给出一个串,求出它所有前缀的最大周期长度之和.

链接

Luogu P3435

题解

分析一下,可以发现我们要求的是所有前缀的最短的相同的前后缀,且还有长度的限制,不能超过字符串的一半。

这个可以联想到$KMP$,所以我们思考如何在$KMP$的基础上维护这个事情。因为$KMP$在往回跳的话,是可以找到所有的相同的前后缀的。所以给定一个前缀,它沿$nex$数组的转移是确定的,我们也就可以维护一个$near[i]$,就是最近能够跳到的长度,也就是相同的前后缀最短值,所以我们就可以$O(1)$的根据$nex$数组计算这个$near$数组,然后得到最后的答案。

代码

点击切换显示状态
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;
}