题解 P4287 【[SHOI2011]双倍回文】
xzyxzy
2018-06-07 15:22:45
~~我竟然是第一个发题解的？！~~
## 广告
[我的博客](https://www.cnblogs.com/xzyxzy/)
博主最近在学习字符串/FFT/退火等算法，有兴趣的同学可以进来玩玩
## 正文
考虑我们用Manacher是怎么求最长回文子串的（如果不会，[请戳我](https://www.cnblogs.com/xzyxzy/p/9150723.html)）
那么如果是双倍回文字串的话，枚举到右子回文串的中心的时候，对应地找到最长双倍回文子串的中心，然后对称地看是否符合条件
举个例子
`#b#a#a#b#b#a#a#b#`
当我枚举到第13位的时候（从1开始），将13作为右子串中心，找到双倍回文子串中心第9位，对称看第5位也满足条件，那么更新答案
我们会发现一些规律
- 左右串中心和全串中心必须要是#
- 能够被右串中心计算到的全串中心是一段区间（原来我以为是一个点，WA了Test6），可以用队列维护（但是对于全是a的会T，所以加上t-h<100）
- 答案就是(i-Centre)*2
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int MAXN=1500000;
int N,l,C,R,p[MAXN],Ans;
int Q[MAXN],h,t;
char s[MAXN];
int main()
{
cin>>N;
char ch=getchar();
while(ch>'z'||ch<'a') ch=getchar();
s[++l]='#';
while(ch>='a'&&ch<='z')
{
s[++l]=ch;s[++l]='#';
ch=getchar();
}
for(int i=1;i<=l;i++)
{
if(i<R)
{
p[i]=min(p[C*2-i],R-i);
while(t-h>100||((i-Q[h])*2>p[Q[h]]&&h<t)) h++;
for(int j=h;j<=t;j++)
if(s[i]=='#'&&s[Q[j]]=='#'&&i-Q[j]+1<=p[i])
Ans=max(Ans,(i-Q[j])*2);
}
else p[i]=1;
while(s[i-p[i]]==s[i+p[i]]&&i-p[i]>=1&&i+p[i]<=l) p[i]++;
if(i+p[i]>R) R=i+p[i],C=i,Q[++t]=i;
}
printf("%d\n",Ans);
return 0;
}
```
刚才卡了一卡，发现能够转移的取6个就可以了，也就是t-h<6
~~作为最短又最快的代码，我有点飘啊。。~~