洛谷P4287 [SHOI2011]双倍回文 题解

题目链接：P4287 [SHOI2011]双倍回文

题意：

记字符串 \(w\) 的倒置为 \(w^R\) 。例如 \((\tt{abcd})^R=\tt{dcba}\) ， \((\tt{abba})^R=\tt{abba}\) 。

对字符串 \(x\) ，如果 \(x\) 满足 \(x^R=x\) ，则称之为回文；例如 \(\tt{abba}\) 是一个回文，而 \(\tt{abed}\) 不是。

如果 \(x\) 能够写成的 \(ww^Rww^R\) 形式，则称它是一个“双倍回文”。换句话说，若要 \(x\) 是双倍回文，它的长度必须是 \(4\) 的倍数，而且 \(x\) ， \(x\) 的前半部分， \(x\) 的后半部分都要是回文。例如 \(\tt{abbaabba}\) 是一个双倍回文，而 \(\tt{abaaba}\) 不是，因为它的长度不是 \(4\) 的倍数。

\(x\) 的子串是指在\(x\)中连续的一段字符所组成的字符串。例如 \(\tt{be}\) 是 \(\tt{abed}\) 的子串，而 \(\tt{ac}\) 不是。

\(x\) 的回文子串，就是指满足回文性质的 \(x\) 的子串。

\(x\) 的双倍回文子串，就是指满足双倍回文性质的 \(x\) 的子串。

你的任务是，对于给定的字符串，计算它的最长双倍回文子串的长度。

\(n \le 500000\)

考虑Manacher求解

对于修改后字符串的 \(i\) 位置的初始回文半径 \(p_i\) （暴力拓展前的半径）

如果 \(i-p_i+1 \le \text{mid}\) ，则存在一个极大双倍回文子串

这个极大双倍回文子串在修改后的串中，

以「以 \(\text{mid}\) 为中心的回文串」的形式存在

注意题目要求的是 \(4\) 倍数的串，则对于刚才的求解方法，

只要限制 \(i\) 为奇数时更新答案、\(\text{mid}\) 和 \(r\)

此时 \(i\) 的回文半径 \(p_i^{\prime}-1\) 一定是偶串的长度

注意 \(r\) 相同时，不要优先更新 \(\text{mid}\)

否则根据贪心，不难发现会失去某些极大值，导致答案出错

这里给个hack（想了我几个小时才想出来）

input:
12
abcbbbbbbbba

output:
8

时间复杂度 \(O(n)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(5e5+15)

char s[N<<1];
int n,p[N<<1];
void Manacher(int l)
{
    int r=1,mid=1,ans=0;
    // 这里的i+=2可以写i++
    // 但是要把下面两个if都加上 (i&1) && ...
    // 没必要。还慢。
    for(int i=1; i<=l; i+=2)
    {
        p[i]=(i<=r)?min(p[(mid<<1)-i],r-i+1):1;
        if(i<=r&&i-p[i]+1<=mid) ans=max(ans,2*(i-mid));
        // cout << i << " " << mid << " " << r << '\n';
        while(s[i-p[i]]==s[i+p[i]]) ++p[i];
        if(i+p[i]-1>r)r=i+p[i]-1,mid=i;
        // cout << i << " " << mid << " " << r << '\n';
    }
    cout << ans << '\n';
    // for(int i=1; i<=l; i++)
    //     cout << p[i] << " \n"[i==l];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("P4287.out","w",stdout);
    cin >> n >> (s+1);
    s[0]='$';
    for(int i=n; i; i--)
        s[i*2+1]='#',s[i*2]=s[i];
    s[1]='#';
    Manacher(n*2+1);
    return 0;
}