This page looks best with JavaScript enabled

「POI2006」Periods of Words-KMP

 ·  ✏️ About  578 words  ·  ☕ 2 mins read · 👀... views

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

比如串 ababababab 都是串 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;
}

cqqqwq
WRITTEN BY
cqqqwq
A student in Software Engineering.


Comments