Cod sursa(job #6341)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 18 ianuarie 2007 22:45:09
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#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]++; v[dr]=max(v[dr],v[st]);
			//printf("%i %i\n",st,dr);
		}

		lim2=st;
		
		sol+=v[i]/2;

		/*for (st++,dr--;st<=lim1;++st,--dr) { 
			v[dr]=max(min(v[st],st-lim2),v[dr]);
			if (!v[dr]) v[dr]=st-lim2;
		}*/
		//for (st=1;st<=n;++st) printf("%i ",v[st]);
		//printf("\n");
	}
	
	//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;

}