Cod sursa(job #6189)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 17 ianuarie 2007 23:11:27
Problema PScPld Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 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]++;
			//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;

}