洛谷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;
}