Pagini recente » Cod sursa (job #704490) | Cod sursa (job #2169307) | Cod sursa (job #3989) | Istoria paginii monthly-2012/runda-7/solutii | Cod sursa (job #61625)
Cod sursa(job #61625)
#include<stdio.h>
#define fin "pscpld.in"
#define fout "pscpld.out"
#define Nmax 2000001
int ret,N,len[Nmax];
char v[Nmax];
inline int minf(int a,int b) { (a<b)?(a):(a=b); return a; }
inline int maxf(int a,int b) { (a>b)?(a):(a=b); return a; }
int main() {
int i,j,tmp,tmp2,nrit=0;
char ch;
freopen(fin,"r",stdin); freopen(fout,"w",stdout);
scanf("%c",&ch);
N=1; v[1]=' ';
while (ch!='\n') {
++N;
v[N]=ch;
scanf("%c",&ch);
++N;
v[N]=' ';
}
++N;
for (i=1;i<=N;++i) {
tmp=len[i];
tmp2=tmp;
while ( v[i-len[i]]==v[i+len[i]] && i-len[i]>=1 && i+len[i]<=N) {
++len[i];
}
--len[i];
while ( v[i-tmp]==v[i+tmp] && i-tmp>=1 && i+tmp<=N) {
len[i+tmp]=maxf(len[i+tmp],minf(len[i-tmp],len[i]-tmp));
++tmp;
}
i+=tmp2;
if (tmp2==0)
++i;
// for (j=1;j<=N;++j)
// fprintf(stderr,"%d ",len[j]);
// fprintf(stderr,"\n");
}
for (i=1;i<=N;++i)
if ( v[i] == ' ' ) {
ret+=len[i]/2;
}
else {
ret+=len[i]/2;
if (len[i]%2!=0)
++ret;
}
fprintf(stderr,"%d\n",nrit);
printf("%d\n",ret);
return 0;
}