Description：

给定一个字符串 $ S$ ，寻求一个最长的形如 $ WW^R WW^R $ 的子串。

$1\leqslant |S|\leqslant 5\times 10^5$

Solution：

先用 $manacher$ 求出 $p[i]$ 表示以 $c[i]$ 和 $c[i+1]$ 之间的为回文中心的最长回文半径，然后发现可以用 $4\times len(x+1,y)$ 更新答案当且仅当 $y-p[y]+1\leqslant x+1$ 并且 $x+p[x]/2\geqslant y$ 。于是把所有位置按 $k-p[k]$ 排序，枚举 $x$ 的值，用双指针把符合条件的 $y$ 加入 $set$ 中，每次查 $x+p[x]/2$ 的前驱更新答案即可。

发现一个优秀得多的做法：由于本质不同的回文子串只有 $O(n)$ 个，因此在 $manacher$ 每次扩展的时候暴力在 $1/4$ 处判断就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

#include<cstring>

using namespace std;

int n;

#define MAXN 500010

char c[MAXN];

int h[MAXN << 1],tot = 0;

char s[MAXN << 1];

int p[MAXN];

int t[MAXN];

bool cmp(int a,int b){return a - p[a] < b - p[b];}

int main()

{ 

	scanf("%d",&n);

	scanf("%s",c + 1);

	s[++tot] = '#';

	for(register int i = 1;i <= n;++i)

	{

		s[++tot] = c[i];

		s[++tot] = '#';

	}

	n = tot;

	register int pos = 1,maxr = 1;

	for(register int i = 1;i <= n;++i)

	{

		if(maxr >= i)h[i] = min(h[2 * pos - i],maxr - i + 1);

		else h[i] = 1;

		while(i - h[i] >= 1 && i + h[i] <= n && s[i - h[i]] == s[i + h[i]])++h[i];

		if(i + h[i] - 1 > maxr)

		{

			maxr = i + h[i] - 1;

			pos = i;

		}

	}

	n = tot / 2;

	for(register int i = 1;i <= n;++i)

	{

		p[i] = h[i * 2 + 1] / 2;

		t[i] = i;

	}

	sort(t + 1,t + 1 + n,cmp);

	set<int> f;f.insert(0x3f3f3f3f); 

	register int ans = 0;

	for(register int i = 1,j = 1;i <= n;++i)

	{

		while(j <= n && t[j] - p[t[j]] <= i)

		{

			f.insert(t[j]);

			++j;

		}

		register set<int>::iterator it = f.upper_bound(i + p[i] / 2);

		if(it == f.begin())continue;

		--it;

		ans = max(ans,*it - i);

	}

	printf("%d\n",ans * 4);

	return 0;

}