[国家集训队] 最长双回文串

[国家集训队] 最长双回文串

题目描述

顺序和逆序读起来完全一样的串叫做回文串。比如 acbca 是回文串，而 abc 不是：abc 的顺序为 abc，逆序为 cba，不相同。

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

输入格式

一行由小写英文字母组成的字符串 $S$。

输出格式

一行一个整数，表示最长双回文子串的长度。

样例 #1

样例输入 #1

baacaabbacabb

样例输出 #1

12

提示

样例说明

从第二个字符开始的字符串 aacaabbacabb 可分为 aacaa 与 bbacabb 两部分，且两者都是回文串。

数据范围

对于 $100\%$ 的数据，$2\le |S|\le 10^5$。

2018.12.10，2018.12.15：感谢 @Ycrpro 提供 hack 数据两组。

//马拉车巧妙运用了回文串的对称性 利用之前循环的信息
//以bba这个回文串为例
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
char arr1[12000000];
char arr2[24000000];
int hw[24000000],ll[24000000],rr[24000000];
int n, l, r, ans, mid;
void build(char* a1, char* a2)
{
	a2[0] = '@', a2[1] = '#';
	for (int i = 2, j = 0; j < n; j++, i += 2)
	{
		a2[i] = a1[j];
		a2[i + 1] = '#';
	}
	//原因为 变成奇序列，从而使任何偶序列变成奇序列，从而回文序列有对称中心
}
//将bba变为@#b#b#b#
int main(void)
{
	cin >> arr1;
	n = strlen(arr1);
	build(arr1, arr2);//将bba变为@#b#b#b#
	int s2 = 2 * n + 1;//delete @ 去掉@的长度。即@#b#b#b#最后一个#对应的下标
	arr2[s2 + 1] = '!';//末尾加！变成@#b#b#b#！ 原因在下文
	for (int i = 1; i <= s2; i++)//hw 回文huiwen
	{//。从arr2【1】=‘#’开始遍历。一直到arr【7】=‘#’遍历找arr【】对应的每个回文
		//半径。回文半径是指如aba中b的回文半径为2，由于在我的处理之下，已经变成奇序列
		if (i <= r )//r为right 当前找到的最靠右的回文串中最后一个字母的位置
			//第一次进入循环时由于r初始化为0
			//如果i在已经找到的回文串的右边之前 
			//由于i的遍历顺序，此时i必定小于mid 因为mid是由之前的i所赋给的。
			hw[i] = min(r - i + 1, hw[mid * 2 - i]);
		else
			hw[i] = 1;//如果i在已经找到的回文串的右边之后，无法利用对称性。或第一次循环时
		//第一个字母arr2【1】=‘#’ 它的回文半径为1
		while (arr2[i - hw[i]] == arr2[i + hw[i]])
			//判断已经找到的回文半径再向左的一个字母和已经找到的回文半径再向右的一个字母
			//此处为添加@与感叹号的原因。如果已经找到的回文半径再向左的一个字母到了@，
			//或者已经找到的回文半径再向左的一个字母到了！，那么说明已经到了边界。不可再扩充回文半径
		{
			++hw[i];//如果满足，则该点的回文半径得到扩充
		}
		if (i + hw[i]-1 > r)//如果该字母找到的回文串最右边的一个字母比当前r对应的字母还靠后
		{
			r = i + hw[i] - 1, mid = i;//更新该字母回文串
		}
		//#b#b#b# 的回文半径为4，回文串的长度为4减1等于三。
		//以下解释hw【i】减1对应该点对应的原回文串长度
	//由于可以看作给回文第一个之前添加#，给每个字母之后都添加#，故回文串必定首尾都有#
	//回文第一个之前添加#，给每个字母之后都添加#。故若字母个数为n，则加上#共2n加1。
	//根据回文半径的定义。回文半径长度为ans。则（ans-1）*2+1等于回文串的总个数。比较得字母个数等于ans-1
		rr[i - hw[i] + 1] = max(rr[i + hw[i] - 1], hw[i] - 1);
		//rr[x]表示x为最左端的饱和回文串的最长长度
		ll[i + hw[i] - 1] = max(ll[i + hw[i] - 1], hw[i] - 1);
		//ll【x]表示x为最右端的饱和回文串的最长长度
		//饱和回文串是最长的不可以再延申的回文串。如在@#b#b#b#中#b#b#b#为饱和回文 而中间#b#为不饱和
	}
	//因此针对饱和回文串的问题进行修正
	for (int i = 3; i <= s2+1; i+=2)
	{
		rr[i] = max(rr[i], rr[i - 2] - 2);
	}
	for (int i = s2-1; i >= 1; i -= 2)
	{
		ll[i] = max(ll[i], ll[i + 2] - 2);
	}
	for (int i = 1; i <= s2+1; i += 2)
	{
		if (rr[i] && ll[i])
			ans = max(ans, ll[i] + rr[i]);
	}
	cout << ans;
	return 0;
	
}