Pagini recente » Cod sursa (job #366751) | Statistici Damian Tudor Christian (damiantudor) | Cod sursa (job #3243709) | Monitorul de evaluare | Cod sursa (job #6189)
Cod sursa(job #6189)
#include<stdio.h>
#define fin "pscpld.in"
#define fout "pscpld.out"
#define Nmax 1000001
int n,sol,sir[2*Nmax],v[2*Nmax];
FILE *in,*out;
int min(int a,int b) { (a>b)?(a=b):(a); return a; }
int max(int a,int b) { (a<b)?(a=b):(a); return a; }
int main() {
int i,st,dr,lim1,lim2;
char c[Nmax];
in=fopen(fin,"r"); out=fopen(fout,"w");
fscanf(in,"%s",&c);
n=1;
for (i=0;c[i]!=NULL;++i) {
sir[++n]=(int)c[i];
++n;
}
//for (i=1;i<=n;++i) printf("%c",sir[i]);
for (i=1;i<=n;++i) {
//printf("%i: ",i);
lim1=i-v[i];
for (st=i-v[i],dr=i+v[i];st>0 && dr<=n && sir[st]==sir[dr];--st,++dr) {
v[i]++;
//printf("%i %i\n",st,dr);
}
lim2=st;
for (st++,dr--;st<=lim1;++st,--dr)
v[dr]=max(min(v[st],st-lim2),v[dr]);
}
for (i=1;i<=n;++i) {
sol+=v[i]/2;
//printf("%i ",v[i]);
}
//printf("\n");
fprintf(out,"%i\n",sol);
fclose(in); fclose(out);
return 0;
}