题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2342

题目分类：字符串，manacher

题意：

定义双倍回文串为形如S1S1rS2S2r的字符串，球一个字符串的最长双倍回文子串。

题解：

先对字符串manacher求出以每个i和i+1位置为中心的最长回文串。

枚举S1r的最后一位。

发现len(x+1,y)*4这个解合法当且仅当：

y-p[y]<=x且y<=x+p[x]/2；

可以将元素按照(x-p[x])排序，递推x的时候依次将y值插入一个set，每次查找x+p[x]/2的前驱即可。

程序：

#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
char str[520000];
int p[520000];
int n;
set<int>st;
set<int>::iterator it;
int d[520000];
inline void manacher()
{
	int mx=0,id;
	for (int i=1;i<=n;i++)
	{
		if(mx>=i)p[i]=min(mx-i,p[2*id-i]);
		else p[i]=0;
		while (str[i+p[i]+1]==str[i-p[i]])p[i]++;
		if(p[i]+i>mx)mx=p[i]+i,id=i;
	}
}
inline bool cmp(int x,int y)
{
	return x-p[x]<y-p[y];
}
int main()
{
	scanf("%d",&n);
	scanf("%s",str+1);
	str[0]='-';
	str[n+1]='+';
	manacher();
	for (int i=1;i<=n;i++)d[i]=i;
	sort(d+1,d+n+1,cmp);
	int cur=1,ans=0;
	for (int i=1;i<=n;i++)
	{
		while (cur<=n&&d[cur]-p[d[cur]]<=i)
		{
			st.insert(d[cur]);
			cur++;
		}
		it=st.upper_bound(i+p[i]/2);
		if(it!=st.begin())
		{
			it--;
			ans=max(ans,((*it)-i)*4);
		}
	}
	printf("%d\n",ans);
	return 0;
}