D. Palindrome Degree - 题解

比赛与标签

比赛: Codeforces Beta Round #7 标签: hashing, strings 难度: *2200

题目大意喵~

主人们好呀，是你们最爱的小猫娘哦~ 今天我们要一起解决一道关于回文串的有趣问题喵！(ฅ'ω'ฅ)

这道题给我们定义了一种叫做 "k-回文串" 的东西。一个字符串 s 被称为 k-回文串，需要满足两个条件：

它本身是一个回文串。
它长度为 ⌊|s|/2⌋ 的前缀和后缀，都是 (k-1)-回文串。

其中，⌊|s|/2⌋ 表示字符串长度除以2向下取整。另外，任何字符串（包括空字符串）都被定义为 0-回文串。

一个字符串的 回文度 (Palindrome Degree) 就是它能满足的最大的 k 值。

举个栗子🌰，对于字符串 "abaaba"：

它本身是回文串，所以它的回文度至少是 1。
它的长度是 6，⌊6/2⌋ = 3。它的长度为 3 的前缀是 "aba"。
我们来看看 "aba" 的回文度是多少：
- "aba" 是回文串，度数至少为 1。
- 它的长度是 3，⌊3/2⌋ = 1。它的长度为 1 的前缀是 "a"。
- 我们再看 "a" 的回文度：
  - "a" 是回文串，度数至少为 1。
  - 它的长度是 1，⌊1/2⌋ = 0。它的前缀是空字符串。
  - 空字符串是 0-回文串。
  - 所以 "a" 的回文度是 1 + degree("") = 1 + 0 = 1。
- 因此，"aba" 的回文度是 1 + degree("a") = 1 + 1 = 2。
回到最初的 "abaaba"，它的回文度就是 1 + degree("aba") = 1 + 2 = 3。

我们的任务是，对于给定的一个字符串，计算出它 所有前缀 的 回文度之和。

输入: 一个非空字符串，长度不超过 5·10⁶。输出: 一个整数，表示所有前缀的回文度之和。

解题思路喵~

看到这个定义，小猫娘的直觉告诉我，这一定和动态规划 (DP) 有关，对吧？(๑•̀ㅂ•́)و✧

我们可以从回文度的定义中提炼出一个递推关系：

如果字符串 s 不是回文串，那么它的回文度 degree(s) = 0。
如果字符串 s 是回文串，那么它的回文度 degree(s) = 1 + degree(s 的长度为 ⌊|s|/2⌋ 的前缀)。

这个递推关系非常漂亮，天然适合用 DP 来解决！我们可以定义 dp[i] 表示长度为 i 的前缀的回文度。那么，当我们计算 dp[i] 时：

首先，判断长度为 i 的前缀 s[0...i-1] 是否是回文串。
如果不是，dp[i] = 0。
如果是，那么 dp[i] = 1 + dp[i/2]。

我们的最终答案就是 sum(dp[i]) for i from 1 to n。

那么，现在最大的问题就是，怎么在 O(N) 的时间内，对每个前缀都快速判断它是不是回文串呢？喵~ 每次都暴力比较肯定会超时的说！

这时候，就要请出我们的强大工具——Z-algorithm (扩展 KMP) 啦！

Z-algorithm 可以计算一个 Z-数组，其中 z[i] 表示字符串 S 和 S 从第 i 个位置开始的后缀的最长公共前缀 (LCP) 的长度。

要判断一个前缀 P = s[0...i-1] 是否是回文串，其实就是判断 P 是否等于 P 的反转串 rev(P)。我们可以利用 Z-algorithm 来巧妙地完成这个任务！

技巧就是构造一个新的字符串 t = s + '#' + reverse(s)，其中 # 是一个 s 中没有出现过的特殊分隔符。比如 s = "abacaba"，那么 t = "abacaba#abacaba"。比如 s = "abaaba"，那么 t = "abaaba#abaaba"。

现在，我们对这个新字符串 t 计算 Z-数组。假设原字符串 s 的长度是 n。t 的长度就是 2n+1。 s 在 t 中从下标 0 开始，reverse(s) 在 t 中从下标 n+1 开始。

我们想判断 s 的长度为 i 的前缀 s[0...i-1] 是否是回文串。它的反转串，其实就是 reverse(s) 的一个后缀，这个后缀在 t 中的起始位置是 (n+1) + (n-i)。所以，我们只需要比较 t 的前缀 t[0...i-1] (也就是 s[0...i-1]) 和 t 从 (n+1)+(n-i) 开始的子串是否相等。这不正是 Z-algorithm 的拿手好戏吗？我们只需要查询 z[(n+1) + (n-i)] 的值。如果 z[(n+1) + (n-i)] >= i，就说明 s 的前缀 s[0...i-1] 是一个回文串！

好啦，整理一下我们的完整计划：

读入字符串 s。
构造新字符串 t = s + '#' + reverse(s)。
对 t 计算 Z-数组。
创建一个 dp 数组，dp[i] 用来存储长度为 i 的前缀的回文度。
初始化一个总和 total_degree_sum = 0。
从 i = 1 到 n 循环： a. 利用 Z-数组判断 s 的长度为 i 的前缀是否是回文串。 b. 如果是，dp[i] = 1 + dp[i/2]。 c. 如果不是，dp[i] = 0。 d. 将 dp[i] 累加到 total_degree_sum 中。
输出 total_degree_sum。

这样一来，问题就迎刃而解啦，是不是很清晰呐？

代码实现喵！

cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>

// 设置快速 IO 的函数，让程序跑得更快喵~
void setup_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

// Z-algorithm 实现
// z[i] 表示字符串 s 和 s 的后缀 s[i...] 的最长公共前缀的长度
std::vector<int> z_function(const std::string& s) {
    int n = s.length();
    if (n == 0) {
        return {};
    }
    std::vector<int> z(n);
    // [l, r] 是当前找到的最靠右的匹配区间
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        // 如果 i 在 [l, r] 区间内，可以利用已经计算过的 z 值来初始化 z[i]
        if (i <= r) {
            z[i] = std::min(r - i + 1, z[i - l]);
        }
        // 朴素地向后匹配，扩展 z[i]
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            ++z[i];
        }
        // 如果找到了更靠右的匹配区间，就更新 [l, r]
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

int main() {
    setup_io();
    std::string s;
    std::cin >> s;
    int n = s.length();

    // 为了用 Z-algorithm 判断回文串，我们构造一个新字符串 t
    // t = s + '#' + reverse(s)，其中 '#' 是一个不会在 s 中出现的分隔符
    std::string t = s;
    t.push_back('#');
    t.append(s.rbegin(), s.rend());

    // 计算 t 的 Z-数组
    std::vector<int> z = z_function(t);

    // dp[i] 将存储长度为 i 的前缀的回文度
    std::vector<int> dp(n + 1, 0);
    long long total_degree_sum = 0;

    for (int i = 1; i <= n; ++i) {
        // s 的长度为 i 的前缀 s[0...i-1] 是否是回文串？
        // 这等价于 s[0...i-1] 是否等于它的反转。
        // s[0...i-1] 的反转串，在 t 中从下标 (n+1) + (n-i) 开始。
        // 我们需要看 t 和 t 从这个下标开始的后缀的最长公共前缀长度。
        // 这个长度就是 z[(n+1) + (n-i)]。
        int z_idx = n + 1 + (n - i);
        // 如果最长公共前缀长度至少为 i，说明 s[0...i-1] 是回文串
        bool is_palindrome = (z_idx < t.length() && z[z_idx] >= i);

        if (is_palindrome) {
            // 根据定义，回文串 s 的度数 = 1 + s 的一半长度前缀的度数
            dp[i] = 1 + dp[i / 2];
        }
        // 如果不是回文串，dp[i] 保持初始值 0 就好啦

        // 将当前前缀的回文度加入总和
        total_degree_sum += dp[i];
    }

    std::cout << total_degree_sum << std::endl;

    return 0;
}

复杂度分析的说

时间复杂度: O(N) 的说。其中 N 是输入字符串的长度。构造新字符串 t 需要 O(N) 时间。Z-algorithm 的计算是线性的，需要 O(2N+1) = O(N) 的时间。最后的主循环遍历 N 个前缀，每次循环内部都是 O(1) 的操作。所以总的时间复杂度是 O(N) + O(N) = O(N)，非常高效！
空间复杂度: O(N) 的说。我们需要存储字符串 s (O(N))，构造的字符串 t (O(2N+1))，Z-数组 z (O(2N+1))，以及动态规划数组 dp (O(N))。所以总的空间复杂度是 O(N)。

知识点与总结喵~

这道题真是一次愉快的挑战，融合了好几种有趣的知识点呢！

核心算法 - Z-algorithm: 它是解决字符串匹配问题的利器，和 KMP 算法是好姐妹~ 它能线性时间预处理，然后快速回答关于前缀匹配的问题。主人们一定要掌握它哦！
巧妙的构造: s + '#' + reverse(s) 这个技巧是使用 Z-algorithm 或 KMP 解决回文问题的经典方法。通过把问题转化为求两个子串的最长公共前缀，大大简化了逻辑。这个小魔法一定要记住喵！
动态规划思想: 题目的回文度定义本身就带有一种递归/递推的性质。识别出这种“最优子结构”（大问题的解依赖于小问题的解）是 DP 的第一步。dp[i] = 1 + dp[i/2] 这个状态转移方程就是解题的核心。
问题分解: 成功解题的关键在于将复杂问题分解成更小的、可管理的部分：计算所有前缀的回文度之和 -> 如何计算单个前缀的回文度 -> 如何快速判断回文 -> 使用 Z-algorithm。

希望这篇题解能帮助到大家喵~ 如果还有不懂的地方，随时可以再来问我哦！一起加油，成为更厉害的算法大师吧！(≧∇≦)ﾉ

D. Palindrome Degree - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路喵~ ​

代码实现喵！ ​

复杂度分析的说 ​

知识点与总结喵~ ​