如果你还不会Manacher：看这里
题意分析
首先，我们发现题目要求最长回文串，自然而然地想到 Manacher。
但是当我们求出最长回文半径 $p_i$ 后，却发现不知道如何进一步做题了。
如果枚举两个回文串分别的回文中心，那么就是一个 $\mathcal O\left(n^2\right)$ 的算法，考虑到 $2\leq \vert S \vert \leq 10^5$，不可取。
我们考虑记录以 $i$ 为右端点的最长回文串长度 $r_i$ 和以 $i$ 为左端点的最长回文串长度 $l_i$，那么答案就是 $\max(l_i+r_i)$。（暂不考虑 Manacher 插入字符）
那么也就是 Manacher 中 $p_i$ 暴力扩展完得到最终 $p_i$ 后，更新 $l_{i-p_i+1}$ 和 $r_{i+p_i-1}$ 。
最后 $\mathcal O\left(n\right)$ 递推 $l_i=\max\left(l_i,l_{i-2}-2\right)$ 和 $r_i=\max\left(r_i,r_{i+2}-2\right)$ 即可。
最长回文串更新
更新
在这一部分，“最长回文串”指的是那些无法继续扩展的回文串，而不是实际意义上的最长回文串。
例如对于 $\texttt{abcbadddaddd}$，$\texttt{abcba}$ 是“最长回文串”，因为其无法继续向两边扩展。
当然，原来意义上的最长回文串仍是此意义下的“最长回文串”，因为其无法继续扩展（$\texttt{dddaddd}$）。
（以下不再使用引号以便于区分）
事实上，我们之前所得到的 $l_{i-p_i+1}$ 和 $r_{i+p_i-1}$ 都是作为最长回文串的，明显还有很多信息没有处理到。
那么为什么直接递推 $l_i=\max\left(l_i,l_{i-2}-2\right)$ 和 $r_i=\max\left(r_i,r_{i+2}-2\right)$ 就行呢？
需要明确的是，我们此时的 $i$ 都是 Manacher 所插入的字符。
先看看 $l_{i-p_i+1}$ 和 $r_{i+p_i-1}$ 具体怎么赋值：
只需要 $l_{i-p_i+1}=\max\left(l_{i-p_i+1},p_i-1\right)$ 即可。（$r_{i+p_i-1}$ 同理）
因为，$p_i$ 包括回文中心 $i$，两边分别共计 $\frac{p_i-1}2$ 个有效字符，总共就是 $p_i-1$（可以自己尝试手推）。
那么此时有值（后面会提到！）的 $l_i,r_i$ 就都是某个最长回文串的边界。
那么我们使用 $l_{i-2}$ 获取到边界，再减去被我们去除的 $2$ 个字符（回文，左右凉拌各一个）就得到了正确的 $l_i$。（$r_i$ 同理）
错误
我当时调的时候，把 $l_{i-p_i+1}$ 和 $r_{i+p_i-1}$ 的更新放在了 Manacher while() 扩展 $p_i$ 的循环内部，导致一直 $\text{WA}$ 在 #5。其实这就涉及到问题了，这会导致之后 $l_i$ 和 $r_i$ 递推时不是最大，进而导致错误。
其实就是因为原本不应该有值的地方有了一个不正确的值。
AC代码
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
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
const int N=1e6;
int top,p[2*N+1],l[2*N+1],r[2*N+1];
char s[2*N+1]={'~'};
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
char ch;
while(cin>>ch){
s[++top]='#';//top=1开始插入#,之后都遍历[1,top]
s[++top]=ch;
}s[++top]='#';
for(int i=1,mid=0,R=0;i<=top;i++){
if(i<R)p[i]=min(p[2*mid-i],R-i);
while(s[i-p[i]]==s[i+p[i]])p[i]++;
l[i-p[i]+1]=max(l[i-p[i]+1],p[i]-1);
r[i+p[i]-1]=max(r[i+p[i]-1],p[i]-1);
if(i+p[i]>R)R=i+p[i],mid=i;
}//注意循环方向和数组越界:l必须从i=3开始,否则i-2会越界
for(int i=top;i>=3;i-=2)r[i]=max(r[i],r[i+2]-2);
for(int i=3;i<=top;i+=2)l[i]=max(l[i],l[i-2]-2);
int ans=0;
for(int i=1;i<=top;i+=2){
if(l[i]>0&&r[i]>0)ans=max(ans,l[i]+r[i]);
}printf("%d\n",ans);
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
