《P3435 [POI 2006] OKR-Periods of Words》

题目描述

一个字符串是由有限个小写英文字母组成的序列。特别地，它可以是一个空序列，即由 0 个字母组成的序列。我们用 A=BC 表示字符串 A 是通过连接字符串 B 和 C（按此顺序）得到的（即一个接一个地写在一起，没有任何空格等）。字符串 P 是字符串 A 的前缀，如果存在一个字符串 B，使得 A=PB。换句话说，A 的前缀是 A 的初始片段。此外，如果 P=A 且 P 不是一个空字符串，我们称 P 是 A 的一个真前缀。

字符串 Q 是 A 的周期，如果 Q 是 A 的一个真前缀且 A 是字符串 QQ 的前缀（不一定是真前缀）。例如，字符串 abab 和 ababab 都是字符串 abababa 的周期。字符串 A 的最大周期是其周期中最长的一个，或者如果 A 没有任何周期，则为一个空字符串。例如，ababab 的最大周期是 abab。abc 的最大周期是空字符串。

任务：编写一个程序：

从标准输入读取字符串的长度和字符串本身，计算其所有前缀的最大周期长度的总和，将结果写入标准输出。

输入格式

标准输入的第一行有一个整数 k (1≤k≤1 000 000) - 字符串的长度。接下来的行中写有恰好 k 个小写英文字母的序列 - 该字符串。

输出格式

标准输出的第一行，你的程序应该输出一个整数 - 输入中给定字符串的所有前缀的最大周期长度的总和。

显示翻译

题意翻译

输入输出样例

输入 #1复制

8
babababa

输出 #1复制

24

说明/提示

（由 ChatGPT 4o 翻译）

代码实现;

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    int k;
    string s;
    cin >> k >> s;

    // 计算前缀函数数组
    vector<int> pi(k);
    for (int i = 1; i < k; ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }
        if (s[i] == s[j]) {
            ++j;
        }
        pi[i] = j;
    }

    long long total = 0;
    for (int n = 1; n <= k; ++n) {
        int max_period = 0;
        int j = pi[n - 1];
        
        // 回溯所有可能的前缀长度
        while (j > 0) {
            // 检查是否满足周期条件：Q是真前缀且A是QQ的前缀
            if (2 * j >= n) {
                max_period = j;
                break; // 找到最大的周期，退出循环
            }
            j = pi[j - 1];
        }
        
        total += max_period;
    }

    cout << total << endl;
    return 0;
}