CVBB ACM Team

pat[0]='@';
for(i=1;i<=n;i++) pat[2*i-1]=ch[i],pat[2*i]='@';
pos=0,r[0]=0;
for(i=1;i<=2*n;i++){
	if(i<=pos+r[pos]) r[i]=min(pos+r[pos]-i,r[pos*2-i]);
	while(i>r[i]&&pat[i+r[i]+1]==pat[i-r[i]-1]) r[i]++;
	if(i+r[i]>pos+r[pos]) pos=i;
}