当前位置：首页 > news >正文

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

news 来源：原创 2024/4/29 3:00:34

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

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

字符串的周期

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

周期

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

border

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

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

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

显然s的最小周期： $n - n e x t [n - 1]$

思路

现在我们回到该题：

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

代码

代码如下

#include <bits/stdc++.h>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;
}

扩展：最大周期长度

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

核心代码

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

例题

[[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 <iostream>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;
}