小编点评

The provided code is a C program that implements a Manacher algorithm to find the longest palindrome substring in a given string. **Algorithm overview:** 1. Preprocess the input string to remove all characters except even characters. 2. Perform a single pass through the input string to compute the longest palindrome substring length. 3. For each possible starting index of the palindrome substring, consider all possible ending indices. 4. For each ending index, check if the substring formed by those two indices is a palindrome. 5. Keep track of the longest palindrome substring found so far. **Key optimizations:** - The code uses a step length of 2, which halves the number of comparisons required to find the longest palindrome substring. - It considers only even-length palindromes, which eliminates a significant portion of the search space. - It uses a two-pointer technique to efficiently compute the longest palindrome substring for each starting index. **Optimization potential:** - The code could be further optimized by using a more efficient algorithm to compute the longest palindrome substring length. - It could also be optimized by using a data structure that allows for efficient access to the substring of a given starting index. **Overall, the code is an efficient implementation of the Manacher algorithm for finding the longest palindrome substring in a given string.**

正文

[SHOI2011]双倍回文 题解

看了一些写回文自动机的大佬的代码，我深感敬畏，于是我转身向Manacher走去

现在荣登最优解第一页……

说实话，这个方法的复杂度是很玄学的，但是加了一些优化之后，就几乎不可能被卡到 \(O(n^2)\) 了。

具体思路如下：

预处理字符串部分就略过吧

• 我们预先跑一次 Manacher 算法，考虑到我们其实只需要偶数的回文串的信息，所以将步长设为 2 就行了。

int M(0), R(0), p;
for (int i(1); i < n; i += 2) {
    p = R > i ? min(R - i + 1, P[(M<<1) - i]) : 1;
    while (s[i + p] == s[i - p]) ++p; // 向两边扩展 
    if (i + p - 1 > R) M = i, R = i + p - 1; // 更新边界
    P[i] = p;        
}

• 接着，我们寻找答案。考虑枚举每一个以 i 为中心的偶数回文串。对于这个回文串，我们枚举其回文左区间内的所有点，判断其能否与右区间内对应的区间构成双倍回文即可。换句话来说，假如我们枚举到了 j，那么如果 j 是左侧的合法答案，就一定有 j + P[j] > i

  额，注意一下，这里的 P[i] 指的是回文串的直径，是包括了中间点的元素的。也就是说，回文串所在区间其实是 (i - P[i], i + P[i])（闭区间！）

  但是，这并不是充要条件。我们考虑这样一种情况

  

  这个时候，j 其实是不合法的，因为绿色的区间才是合法的区间（合法的区间一定是被 i 的回文区间完全包含的！）。所以，对于合法区间的中点，一定在 i 的做右区间中点的左边或者右边。那么实际上，我们只需要枚举 (i, i + P[i]/2] 作为中点即可。

• 小小的优化：我们需要最大值，所以令答案为 ans，我们枚举 (i + ans, i + P[i]/2] 即可。而且，我们需要的偶数的回文串，所以步长也可以设为 2 来枚举的。

参考代码：

#include <stdio.h>

#define N 1000006

int n, P[N];
char s[N];

inline int min(int x, int y) {
    return x < y ? x : y;
}
inline int max(int x, int y) {
    return x > y ? x : y;
}

int main() {
    scanf("%d", &n);

    char tmp;
    do tmp = getchar(); while (tmp < 'a');
    s[0] = '^', s[1] = '#', s[2] = tmp, s[3] = '#';
    for (int i(2); i <= n; ++i) {
        s[(i<<1)] = getchar(), s[(i<<1)|1] = '#';
    }

    // printf("%s\n", s);

    int ans(0);
    int M(0), R(0), p;
    n = (n<<1) + 2;
    for (int i(1); i < n; i += 2) {
        p = R > i ? min(R - i + 1, P[(M<<1) - i]) : 1;
        while (s[i + p] == s[i - p]) ++p; // 向两边扩展 
        if (i + p - 1 > R) M = i, R = i + p - 1; // 更新边界
        P[i] = p;        
    }
    // 寻找答案
    for (int i(1); i < n; i += 2) {
        int p = P[i] / 2 + 1;
        for (int r(ans); r < p; r += 2) {
            if (P[i + r] > r && P[i - r] > r) ans = r;
        }
    }
    printf("%d\n", ans + ans);
    return 0;
}