zoj 2744 Palindromes

zoj 2744 Palindromes

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=5010;char s[N*2],str[N];int p[N*2],n;void init(){ n=strlen(str); s[0]='$'; s[1]='#'; for(int i=0; i<n; i++) { s[i*2+2]=str[i]; s[i*2+3]='#'; } n=n*2+2; s[n]='';}void Manacher(){ int k=0; int pos; for(int i=1;i<n; i++) { if(k>i) p[i]=min(p[2*pos-i],k-i); else p[i]=1; while(s[i+p[i]]==s[i-p[i]]) p[i]++; if(p[i]+i>k) k=p[pos=i]+i; }}int main(){ while(~scanf("%s",str)) { init(); Manacher(); int res=0; for(int i=1;i<n; i++) res+=(p[i]/2); printf("%dn",res); } return 0;}