标签：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;
}