[国家集训队] 最长双回文串

标签: #manacher #DP #单调队列
原题目: luogu-P4555
简要描述: 逻辑题目

我觉得这个题目的核心在于: 在manacher算法后,找到双回文,暴力枚举O(n2)O(n^2)

怎么暴力: 枚举双回文的分割位置.左侧长度,通过枚举p[j] ,j <i,得到

显然我们要在O(n)的实现,使用构造法,

  • l[i] 表示以i为结尾的最长的回文串

  • r[i] 表示以i为开头的最长的回文串

  • 显然l[i] 可以由 p[j] 计算出来

如果i位置是回文的结尾,那么i必然在一对[C,R]之间,则l[i] = 2*(i-C) + 1, l[i] = 1,则l[i]的值,就是由左侧的所有满足条件的[C,R]得到.

发现[C,R],具有二分性质(单调性):

  • [C,R]对于i来说满足的条件C<=i<R
  • 如果一对C,R 对i没有用R<iR<i,则对于后面的所有的i+k,都没有用,(对于R来说有单调满足)
  • 在满足的[C,R],找到最小的C,

问题变成了求i左侧的C,R的集合

现在我来证明单调性是满足的:

  • 按C从小到大排序,显然C是单调递增的,
  • (Ci,Ri)(C_i,R_i),(Cj,Rj)(C_j,R_j),j>ij>i,那么显然Ci<CjC_i< C_j,
  • 如果Ri>RjR_i>R_j,那么显然RjR_j不可能成为后面元素的最优解,可以删除
  • 所以备选集合RR是单调增加的

所以我们可以用单调队列来维护这个集合

  • 维护一个单调队列,队列中元素是单调递增的
  • 如果新元素比队尾元素小,则队尾元素不可能成为后面元素的最优解,可以删除
  • 如果新元素比队尾元素大,则队尾元素可能成为后面元素的最优解,可以保留

取元素的时候,从队头开始取,直到找到第一个满足条件的元素: R>iR >i

更简单,递推

上面的代码核心思路是正确的（使用 Manacher 算法处理回文半径），但是为了计算“左边最长回文”和“右边最长回文”，你使用了双向队列（Deque）和两次遍历的复杂逻辑，这使得代码显得冗长且难以维护。

其实，这道题有一个非常经典的线性递推（DP）优化，可以替代队列逻辑：

如果一个位置 ii 是某个长回文串的边界，那么 i±2i \pm 2 也是其内部子回文串的边界。

下面是重构后的代码。我移除了所有复杂的结构体和队列，利用 Manacher 算出的半径数组 p，通过简单的递推直接求出每个分割点的最优解。

重构后的 C++ 代码

cpp
copy 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

        #include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 100005;

// 定义 Manacher 变换后的最大长度
const int SZ = MAXN * 2 + 5;

// s: 原始字符串
// t: 变换后的字符串
// p: Manacher 半径数组
// l[i]: 以 t[i] 为 **结尾** 的最长回文子串长度
// r[i]: 以 t[i] 为 **开头** 的最长回文子串长度
char s[MAXN], t[SZ];
int p[SZ], l[SZ], r[SZ];

int main() {
    // 1. 快速 IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 2. 读取输入
    if (scanf("%s", s) != 1) return 0;

    // 3. 构造 Manacher 变换字符串
    // 例如: "abc" -> "$#a#b#c#^"
    int n = strlen(s);
    int m = 0;
    t[m++] = '$';
    t[m++] = '#';
    for (int i = 0; i < n; ++i) {
        t[m++] = s[i];
        t[m++] = '#';
    }
    t[m++] = '^';
    t[m] = '\0';

    // 4. Manacher 算法核心
    // 计算每个中心点的最大回文半径 p[i]
    int center = 0, right = 0;
    for (int i = 1; i < m - 1; ++i) {
        int mirror = 2 * center - i;
        if (i < right) 
            p[i] = min(right - i, p[mirror]);
        else 
            p[i] = 1;

        while (t[i + p[i]] == t[i - p[i]]) 
            p[i]++;

        if (i + p[i] > right) {
            right = i + p[i];
            center = i;
        }

        // --- 核心优化点 1: 记录边界 ---
        // p[i]-1 是回文串的实际长度
        // 该回文串在 t 中的范围是 [i - p[i] + 1, i + p[i] - 1]
        
        int left_boundary = i - p[i] + 1;
        int right_boundary = i + p[i] - 1;

        // 更新以 left_boundary 开头的最长回文
        r[left_boundary] = max(r[left_boundary], p[i] - 1);
        // 更新以 right_boundary 结尾的最长回文
        l[right_boundary] = max(l[right_boundary], p[i] - 1);
    }

    // 5. 递推传播 (替代原本的队列/排序逻辑)
    // 如果位置 i 有一个长度为 L 的回文开头，那么 i+2 必然有一个长度为 L-2 的回文开头(同心圆原理)
    // 步长为 2 是因为 t 串中每两个字符中间隔着一个 '#'
    
    // 从左向右推 r (Start)
    for (int i = 2; i < m - 2; i += 2) {
        r[i] = max(r[i], r[i - 2] - 2);
    }
    
    // 从右向左推 l (End)
    for (int i = m - 3; i >= 2; i -= 2) {
        l[i] = max(l[i], l[i + 2] - 2);
    }

    // 6. 统计答案
    // 我们需要在 '#' 处切分，因为 '#' 对应原串字符之间的空隙
    // 只有偶数索引是 '#'
    int ans = 0;
    for (int i = 2; i < m - 2; i += 2) {
        if (l[i] > 0 && r[i] > 0) { // 题目要求两部分都非空
            ans = max(ans, l[i] + r[i]);
        }
    }

    printf("%d\n", ans);

    return 0;
}

优化的关键点 (Why is it cleaner?)

  1. 移除了 struct Node 和 queue：

    • 原代码试图通过队列来寻找“满足条件的最佳回文”。
    • 新代码利用回文的包含性质：如果 abacaba 是回文，去掉首尾的 a，剩下的 bacab 也是回文。这意味着，如果我们算出某个位置开始的最长回文长度为 LL，那么该位置向内缩一格（在变换串中是+2）必然存在一个长度为 L−2L-2 的回文。
    • 代码体现：r[i] = max(r[i], r[i-2] - 2)。这直接将 O(Nlog⁡N)O(N \log N) 或复杂的 O(N)O(N) 逻辑简化为了几行简单的循环。

  2. 单一职责：

    • Manacher 循环只负责算 p[] 和记录最外层边界。
    • 递推循环负责填补内部缺失的长度信息。
    • 最后循环负责找最大值。

  3. 变量命名清晰：

    • l[i] (left max length ending at i) 和 r[i] (right max length starting at i) 直观对应题目要求的 XX 和 YY 两部分。

  4. 去除了冗余逻辑：

    • 不需要像原代码那样把 Manacher 分成“从左到右”和“从右到左”写两遍。Manacher 算法本身就是对称的，一次遍历得到半径数组 p 即可推导出所有信息。