Cod sursa(job #639686)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 23 noiembrie 2011 19:45:04
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<stdio.h>
#include<string>

#define maxn 1000005

FILE*f=fopen("pscpld.in","r");
FILE*g=fopen("pscpld.out","w");

int n,st,dr,i,j,nrpal;
int D[maxn<<1];
char sir[maxn];

inline int min ( int a , int b ){
	return a <= b ? a : b;
}

int main () {
	
	fscanf(f,"%s",sir+1);
	n = strlen(sir+1);
	
	st = 1; dr = 0;
	for ( i = 1 ; i <= n + n ; ++i ){
		j = (i+1)>>1;
		if ( (!(i & 1)) && sir[j] != sir[j+1] )	continue ;
		if ( j <= dr ){
			if ( i & 1 )	
				D[i] = min(D[((st+dr-j)<<1)-1],dr-j);
			else	
				D[i] = min(D[((st+dr-j)<<1)-2],dr-j);
			if ( D[i] + j >= dr ){
				if ( i & 1 ){
					st = j - D[i]; dr = j + D[i];
				}
				else{
					st = j - D[i] + 1; dr = j + D[i];
				}
				for ( ; st > 1 && dr < n && sir[st-1] == sir[dr+1] ; --st , ++dr , ++D[i] );
			}
		}
		else{
			if ( i & 1 ){
				st = dr = j;
				for ( ; st > 1 && dr < n && sir[st-1] == sir[dr+1] ; --st , ++dr , ++D[i] );
			}
			else{
				st = j; dr = j+1; D[i] = 1;
				if ( sir[st] == sir[dr] ){
					for ( ; st > 1 && dr < n && sir[st-1] == sir[dr+1] ; --st , ++dr , ++D[i] );
				}
				else{
					D[i] = 0;
				}
			}
		}
	}
	
	for ( i = 1 ; i <= n + n ; ++i ){
		D[i] = D[i]<<1;
		D[i] += i&1;
	}
	
	for ( i = 1 ; i <= n + n ; ++i ){
		if ( i & 1 )	nrpal += (D[i]+1)>>1;
		else	nrpal += (D[i]>>1);
	}
	
	fprintf(g,"%d\n",nrpal);
	
	fclose(f);
	fclose(g);
	
	return 0;
}