[POI2006] OKR-Periods of Words——最大周期长度(扩展最小周期长度)

[POI2006] OKR-Periods of Words——最大周期长度(扩展最小周期长度)

[原题链接](P3435 [POI2006] OKR-Periods of Words - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

---

字符串的周期

讲这道题之前，我们先聊一聊字符串的周期。我们要明确周期和border两个概念

周期

对字符串$s$和$0<p\le \left|s\right|$，若$s[i]=s[i+p]$对所有 $i\in [0,\le \left|s\right|-p-1]$ 成立，则称$p$是$s$的周期

border

对字符串$s$和$0<p<\left|s\right|$，若s长度为r的前缀和长度为r的后缀相等，就称s长度为r的前缀是s的border

由s由长度为r的border可以推导出$\le \left|s\right|-r$是s的周期

根据kmp的next数组，可以得到s(下标从0开始）的所有border长度，next[n-1]，next[next[n-1]-1],…

显然s的最小周期： $n-next[n-1]$

思路

现在我们回到该题：

该题就是让我们求字符串$s_1$的最小周期

代码

代码如下

#include 

using namespace std;

const int N = 1e6 + 10;

char c[N];
int ne[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    // 字符串下标从1开始
    cin >> n >> c + 1;
    // 获取next数组
    for (int i = 2, j = 0; i <= n; i ++) {
        while (j && c[i] != c[j + 1])
            j = ne[j];
        if (c[i] == c[j + 1]) {
            j ++;
            ne[i] = j;
        }
    }
    cout << n - ne[n];

    return 0;
}

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

扩展：最大周期长度

让每一个next数组的值都是最短前缀

核心代码

int j = n;
// 转换为最短前缀
while (ne[j]) 
    j = ne[j];
// 记忆化存储
if (ne[i])  ne[i] = j;
// 最大周期长度
len = n - j;
1
2
3
4
5
6
7
8

例题

[[POI2006] OKR-Periods of Words](P3435 [POI2006] OKR-Periods of Words - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

分析

求每个子串的最大周期长度

样例分析

bab 2

baba 2

babab 4

bababa 4

bababab 6

babababa 6

参考代码

#include 

using namespace std;

const int N = 1e6 + 10;
typedef long long LL;

char s[N];
LL ne[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n >> s + 1;
    for (int i = 2, j = 0; i <= n; i ++) {
        while (j && s[i] != s[j + 1])
            j = ne[j];
        if (s[i] == s[j+1])
            j ++;
        ne[i] = j;
    }
    LL ans = 0;
    for (int i = 2; i <= n; i ++) {
        int j = i;
        while (ne[j]) {
            j = ne[j];
        }
        if (ne[i])  ne[i] = j;
        ans += i-j;
    }
    cout << ans << endl;

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