manacher算法

const int LEN=110005;
const int N=LEN*2;
int p[N];
char str[LEN], tmp[N];
//p[i]表示以str[i]为中心的回文往右延伸的 最长长度
void manacher(char* str, int* p){
	int n=strlen(str), i, id, mx;
	for(p[mx=id=0]=i=1; i<n; i++){
		p[i]=mx>i?min(p[2*id-i], mx-i+1):1;
		while(i+p[i]<n&&i-p[i]>=0&&str[i+p[i]]==str[i-p[i]]) p[i]++;
		if(mx<i+p[i]-1){
			id=i;
			mx=i+p[i]-1;
		}
	}
}
//求str的最长回文的长度
int maxPalindrome(char* str){
	int ans=0;
	int i, n;
	for(i=0, n=strlen(str); i<n; i++){
		tmp[2*i]='#';
		tmp[2*i+1]=str[i];
	}
	tmp[2*i]='#';
	tmp[2*i+1]='\0';
	n=n*2+1;
	manacher(tmp, p);
	for(i=0; i<n; i++){
		if(ans < p[i]-1){
			ans = p[i]-1;
		}
	}
	return ans;
}