P3435 [POI 2006] OKR-Periods of Words

时间限制: 1.00s    内存限制: 128.00MB

题目描述

一个字符串是由小写英文字母组成的有限序列。特别地，它也可以是空序列（即长度为 0 的序列）。

如果字符串 A 是通过字符串 B 和 C 按顺序连接（中间没有任何间隔符号）得到的，我们表示为 A=BC。

如果存在一个字符串 B 使得 A=PB，那么字符串 P 是字符串 A 的前缀。此外，如果 P=A 且 P 不是空字符串，我们称 P 是 A 的真前缀。

如果 Q 是 A 的真前缀，并且 A 是字符串 QQ 的前缀（不一定是真前缀），那么字符串 Q 是 A 的周期。例如，字符串 abab 和 ababab 都是 abababa 的周期。

字符串 A 的最大周期是其最长的周期，如果 A 没有周期，则为空字符串。例如，ababab 的最大周期是 abab；abc 的最大周期是空字符串。

---

任务：

编写一个程序，计算该字符串所有前缀的最大周期长度之和。

输入格式

第一行包含一个整数 k，表示字符串的长度。

接下来的一行包含一个由 k 个小写英文字母组成的字符串。

输出格式

单独一行输出一个整数，表示输入字符串所有前缀的最大周期长度之和。

题意翻译

输入输出样例

输入 #1复制运行

8
babababa

输出 #1复制运行

24

说明/提示

（由 Gemini 2.5 Flash 翻译，人工审核）

数据范围

对于所有数据，1≤k≤106。

思路：

这道题是 KMP 算法的经典应用，利用next 数组（代码里的 n 数组）找字符串每个前缀的最长相等真前后缀，再通过追溯找到最小相等前后缀，用前缀长度 - 最小相等前后缀长度得到该前缀的最大周期长度，最后累加所有前缀的结果就是答案。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n[1000005]; // KMP的next数组，存前i个字符的最长相等真前后缀长度
int j, cd;      // j是匹配指针，cd是字符串长度
ll ans;         // 答案（用long long防溢出）
char s[1000005];// 存储字符串，从下标1开始
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); // 输入加速，适配大数据
    cin >> cd >> s + 1;

    // 第一步：构建KMP的next数组
    for (ll i = 1; i < cd; ++i) {
        while (j && s[j+1] != s[i+1]) j = n[j]; // 匹配失败则回退
        if (s[j+1] == s[i+1]) j++; // 匹配成功，指针后移
        n[i+1] = j; // 记录最长相等前后缀长度
    }

    // 第二步：追溯找最小相等前后缀，累加每个前缀的最大周期长度
    for (ll i = 1; i <= cd; ++i) {
        j = i;
        while (n[j]) j = n[j]; // 一直追溯到无相等前后缀（n[j]=0）
        if (n[i]) n[i] = j;    // 记忆化，避免重复追溯
        ans += i - j;          // 最大周期长度 = 前缀长度 - 最小相等前后缀长度
    }

    cout << ans;
    return 0;
}