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

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

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

---

字符串的周期

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

周期

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

border

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

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

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

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

思路

现在我们回到该题：

该题就是让我们求字符串 s 1 s_1 s1​的最小周期

代码

代码如下

#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 ))

分析

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

样例分析

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