hdu_3068_최 장 답장 (Manacher)

제목 연결:http://acm.hdu.edu.cn/showproblem.php?pid=3068
제목: 가장 긴 답장 문자열 을 구 할 수 있 는 문자열 을 드 리 겠 습 니 다.
문제 풀이: 데이터 양 이 비교적 많 고 폭력 O (n2) 는 시간 을 초과 하여 직접 말 에 올 라 수레 를 끌 고 모형 문 제 를 풀 수 있다.

#include<cstdio>
#include<cstring>
#define min(a,b) (a)>(b)?(b):(a)
#define max(a,b) (a)>(b)?(a):(b)
const int maxn = 110005;//     
struct Manacher{
	char str[maxn<<1];
	int p[maxn<<1],len,mx,id,tl,ans,i;
	//bool pre[maxn],suf[maxn];// ( ) ( ( )p[i]-1   )      
    //void init(int len){for(int i=0;i<=len;i++)suf[i]=0,pre[i]=0;}
	int maxlen(char *s){
		len=strlen(s),mx=0,id=0,tl=0,str[tl++]='$',str[tl++]='#';
		for(i=0;i<len;i++)str[tl++]=s[i],str[tl++]='#';
		for(i=2,str[tl]=0,ans=0;i<tl;i++){
			p[i]=mx>i?min(p[(id<<1)-i],mx-i):1;
			while(str[i-p[i]]==str[i+p[i]])p[i]++;
            if(i+p[i]>mx)mx=i+p[i],id=i;
			ans=max(ans,p[i]);
			//if(i-p[i]==0)pre[p[i]-1]=true;  
            //if(i+p[i]==len*2+2)suf[p[i]-1]=true;
		}
		return ans-1;
	}
}M;
char s[maxn];
int main(){
	while(~scanf("%s",s)){
		printf("%d
",M.maxlen(s));
	}
	return 0;
}