Cod sursa(job #6179)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 17 ianuarie 2007 22:43:17
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 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 max(int a,int b) { (a<b)?(a=b):(a); return a; }

int main() {
int i,st,dr;
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) {
		
		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]);
		}
	}
	
	for (i=1;i<=n;++i) {
		sol+=v[i]/2; 
		//printf("%i ",v[i]);
	}

	fprintf(out,"%i\n",sol);

	fclose(in); fclose(out);

	return 0;

}