板子|manacher算法

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=11000005;
char s[maxn*3],tmp[maxn*3];
int p[maxn*3];
int create(){//插入特殊字符，将新的字符串tmp长度变为奇数。  并返回长度 
	int len=strlen(s);
	tmp[0]='$';//防止越界 
	tmp[1]='#';
	int j=2;
	for(int i=0;i<len;i++){
		tmp[j++]=s[i];
		tmp[j++]='#';
	}
	tmp[j]='';//防止越界
	return j;
	
}
int manacher(){
	int len=create(),ans=-1;
	int id,mx=0;/*回文串最右端点*/
	for(int i=1;i<len;i++){
		if(i<mx) p[i]=min(mx-i,p[2*id-i]);
		else p[i]=1;
		while(tmp[i-p[i]]==tmp[i+p[i]]) p[i]++;
		if(mx<i+p[i]){
			id=i;
			mx=i+p[i];
		}
		ans=max(ans,p[i]-1);//字符串长度就是p[i]-1
		                    //证明：tmp中的长度为2*p[i]-1
							//其中特殊字符比原字符长度多1. 
	}
	return ans;
}
int main(){
	scanf("%s",s);
	printf("%d",manacher());
	return 0;
}