HDU ACM 4513 吉哥系列故事——完善队形II->求最长回文串（manacher算法）

HDU ACM 4513 吉哥系列故事——完美队形II->求最长回文串（manacher算法）
分析：该題可以通过求最长回文串的方法来解决；求最长回文串使用manacher算法，O(n)时间复杂度。
注意：while(a[i-len[i]]==a[i+len[i]] && a[i-len[i]]<=a[i-len[i]+2])这里多出的判断a[i-len[i]]<=a[i-len[i]+2]即为该題的限制从左到中保证身高不降，因在回文串的计算过程中添加了额外的字符，所以这里是i-len[i]+2而不是i-len[i]+1，以避开添加的字符。

#include<iostream>
using namespace std;

#define N 100010
int len[N<<1];
int a[N<<1];

int Manacher(int n)
{
	int i,ans,mx,po;

	ans=po=mx=0;
	for(i=1;i<=(n<<1)+2;i++)
	{
		if(mx>i)
			len[i]=mx-i<len[(po<<1)-i]?mx-i:len[(po<<1)-i];
		else
			len[i]=1;
		while(a[i-len[i]]==a[i+len[i]] && a[i-len[i]]<=a[i-len[i]+2])   //因为有填充字符'#'，所以要+2。
			len[i]++;
		if(i+len[i]>mx)
		{
			mx=i+len[i];
			po=i;
		}
		ans=ans>len[i]?ans:len[i];
	}
	return ans-1;
}

int main()
{
	int T,n,i;


	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		a[0]=-100;
		for(i=1;i<=n<<1;i+=2)
		{
			a[i]=-200;              //相当于'#'
			scanf("%d",&a[i+1]);
		}
		a[i]=-200;                 //相当于'#'
		a[i+1]=-300;
		printf("%d\n",Manacher(n));
	}
	return 0;
}