HDu 3068最長回文Manacherアルゴリズム

クリックしてリンクを開く
リファレンス
Manacherはマッチングした最右位置と対応する対称中心利用と対称性を記録することによっていくつかの無駄な比較をスキップする.

#include 
#include 
#include 
#include  
using namespace std;
const int M =111000;
char s[M];
char t[2*M]; //            
int p[2*M];// p[i]  i             
int len;
void Init()
{
	int i;
	len=strlen(s);
	t[0]='@';//     
	for(int i=1;i<=2*len;i+=2)
	{
		t[i]='#';
		t[i+1]=s[i/2];
	 }
	 t[2*len+1]='#';//    
	 t[2*len+2]='$';//    
	 t[2*len+3]=0;//    
	 
	len=2*len+1;//          
}
void MANACHER()
{
	int mx=0,ans=0,po=0;// i    p po po     mx 
	for(int i=1;i<=len;i++)
	{
		if(mx>i)
		{
			
			p[i]=min(p[2*po-i],mx-i); // i  po     (i+j)/2=po  j=2*po-i	
			
			//  1 j-len[j]~~i+len[j]   po   -> lem[i]>=len[j] (       )
			
			//  2   i+len[j]>mx       i-(mx-i)~~i+(mx-i)       mx             (       )
			
		
		
		}
		else
		{
			p[i]=1;//mx                     
			
		}
		while(t[i-p[i]]==t[i+p[i]]) 
		p[i]++;
		if(p[i]+i>mx)//update
		{
			mx=p[i]+i;
			po=i;
		}
		ans=max(ans,p[i]);
	}
	ans-=1;//         2*p[i]-1  '#'         1 (   ） x+(x-1)==2*p[i]-1 x=p[i]                p[i]-1 
	printf("%d
",ans);
} 
int main()
{
	while(scanf("%s",s)!=EOF)
	{
		
		Init();	
		MANACHER(); 
		
		

	}
	
	return 0;
}