学步园

        网上说求回文串有三种算法，lcs的n^2算法，后缀数组n*log(n)，manacher的时间复杂度是O(n)的。

我以前只会n^2的算法，刚学的这个算法。

void manacher(){
	int id,mx=0,len;
	len=strlen(cstr);
	for(int i=1;i<len;i++){
		if(mx>i) 
			p[i]=min(p[id*2-i],mx-i);
		else p[i]=1;
		for(;cstr[i+p[i]]==cstr[i-p[i]];p[i]++);
		ans=max(ans,p[i]);
		if(mx<p[i]+i)
			mx=p[i]+i,id=i;
	}
}

       代码的实现上很简单，也很好写。