Description：

输入长度为 $n$ 的串 $S$ ，求 $S$ 的最长双回文子串 $T$ ，即可将 $T$ 分为两部分 $X$ ， $Y$ ， $(∣X∣,∣Y∣\ge 1)$ 且 $X$ 和 $Y$ 都是回文串。

$2\le |S|\le 10^5$

Solution：

先用 $manacher$ 求出所有的回文半径，那么一个 $DP$ 思路是记录每个点前面的最长回文和后面的最长回文，最后统计答案时加在一起，但我们显然不可能把回文区域中所有端点打上标记，于是我们只在极大回文端点打上标记，标记一定打在了 $'\#'$ 上，最后递推地统计一边即可得到每个点作为端点的最长回文长度。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXL 100010

char c[MAXL];

char t[MAXL << 1];

int r[MAXL << 1];

int fl[MAXL << 1],fr[MAXL << 1];

int main()

{

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

	int l = strlen(c + 1);

	int n = 0;

	t[++n] = '#';

	for(int i = 1;i <= l;++i)

	{

		t[++n] = c[i];

		t[++n] = '#';

	}

	int maxr = 0,pos = 0;

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

	{

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

		else r[i] = 1;

		while(i + r[i] <= n && i - r[i] >= 1 && t[i + r[i]] == t[i - r[i]])++r[i];

		if(i + r[i] > maxr)

		{

			maxr = i + r[i];

			pos = i;

		}

		fr[i + r[i] - 1] = max(fr[i + r[i] - 1],r[i] - 1);

		fl[i - r[i] + 1] = max(fl[i - r[i] + 1],r[i] - 1);

	}

	for(int i = n;i >= 1;i -= 2)fr[i] = max(fr[i],fr[i + 2] - 2);

	for(int i = 1;i <= n;i += 2)fl[i] = max(fl[i],fl[i - 2] - 2);

	int ans = 0;

	for(int i = 1;i <= n;i += 2)ans = max(ans,fl[i] + fr[i]);

	cout << ans << endl;

	return 0;

}