标签：STL，Manacher
题目
Description
Input
输入分为两行，第一行为一个整数，表示字符串的长度，第二行有个连续的小写的英文字符，表示字符串的内容。
Output
输出文件只有一行，即：
输入数据中字符串的最长双倍回文子串的长度，如果双倍回文子串不存在，则输出0。
Sample Input
16
ggabaabaabaaball
Sample Output
12
HINT
N<=500000
题意
求一个字符串的最长双倍回文字串长度
分析
前置技能：Manacher算法
先跑一边Manacher算法，求出p数组（以i位置为中心的最长回文半径）
枚举x为对称轴（实际上对称轴位于x和x+1之间，因为要求双倍回文字串长度为4的倍数）
那么我们可以用x表示双倍回文串中初始串的左边界，y表示右边界
显然，需要满足两个条件
-
y-p[y]<=x
-
x+(p[x]/2)>=y
p数组预处理出之后，按照y-p[y]的大小排序
用set查找并更新答案
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=5e5+6;
char ch[maxn];int p[maxn],que[maxn<<1],n,ans;
set<int> t;
void manacher(){
int Max=0,id;
rep(i,1,n){
if(Max>=i)p[i]=min(Max-i,p[2*id-i]);else p[i]=0;
while(ch[i+p[i]+1]==ch[i-p[i]])p[i]++;
if(p[i]+i>Max)Max=p[i]+i,id=i;
}
}
inline bool cmp(int a,int b){return (a-p[a])<(b-p[b]);}
int main()
{
n=read();
scanf("%s",ch+1);
ch[0]='#';
manacher();
rep(i,1,n)que[i]=i;
sort(que+1,que+n+1,cmp);
int now=1;
rep(i,1,n){
while(now<=n&&que[now]-p[que[now]]<=i)t.insert(que[now++]);
set<int>::iterator tmp=t.upper_bound(i+p[i]/2);
if(tmp!=t.begin())ans=max(ans,(*--tmp-i)*4);
}
cout<<ans<<endl;
return 0;
}
