Cod sursa(job #61624)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 20 mai 2007 10:23:59
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<stdio.h>
#define fin  "pscpld.in"
#define fout "pscpld.out"
#define Nmax 2000001

int ret,N,len[Nmax];
char v[Nmax];

int minf(int a,int b) { (a<b)?(a):(a=b); return a; }
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;
}