Cod sursa(job #934694)

Utilizator deividFlorentin Dumitru deivid Data 31 martie 2013 00:29:42
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<stdio.h>
#include<cstring>

#define maxn 1000005

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

int n;
int lung[maxn];
char sir[maxn];

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

int main () {
	
	fscanf(f,"%s",sir+1); n = strlen(sir+1);
	
	int st = 0,dr = 0;
	for ( int i = 1 ; i <= n ; ++i ){
		
		if ( i <= dr ){
			lung[i] = min(lung[st+dr-i],dr-i+1);
			int p = i-lung[i]+1,u = i+lung[i]-1;
			while ( p > 1 && u < n && sir[p-1] == sir[u+1] ){
				++lung[i];
				--p; ++u;
			}
			if ( u > dr ){
				st = p,dr = u;
			}
		}
		else{
			lung[i] = 1;
			int p = i,u = i;
			while ( p > 1 && u < n && sir[p-1] == sir[u+1] ){
				++lung[i];
				--p; ++u;
			}
			st = p,dr = u;
		}
	}
	
	long long sol = 0;
	for ( int i = 1 ; i <= n ; ++i ){
		sol += lung[i];
	}
	
	st = dr = 0;
	for ( int i = 1 ; i < n ; ++i ){
		if ( sir[i] != sir[i+1] ){
			lung[i] = 0;
			continue ;
		}
		
		if ( i < dr ){
			lung[i] = min(lung[st+dr-i-1],dr-i);
			int p = i-lung[i]+1,u = i+lung[i];
			while ( p > 1 && u < n && sir[p-1] == sir[u+1] ){
				++lung[i];
				--p; ++u;
			}
			if ( u > dr ){
				st = p,dr = u;
			}
		}
		else{
			lung[i] = 1;
			int p = i,u = i+1;
			while ( p > 1 && u < n && sir[p-1] == sir[u+1] ){
				++lung[i];
				--p; ++u;
			}
			st = p,dr = u;
		}
	}
	
	for ( int i = 1 ; i < n ; ++i ){
		sol += lung[i];
	}
	
	fprintf(g,"%lld\n",sol);
	
	fclose(f);
	fclose(g);
	
	return 0;
}