Cod sursa(job #479395)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 23 august 2010 21:04:22
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define Nmax 1000010
using namespace std;

long long L1[Nmax],L2[Nmax],n,i,sol,pal;
char v[Nmax];

int main()
{
	freopen("pscpld.in","r",stdin);
	freopen("pscpld.out","w",stdout);
	
	scanf("%s",v+1);
	
	pal = 1 ;  
	
	n = strlen(v+1);
	
	sol = n ;
	
	if( v[1] == v[2] ) L1[1] = 1 ;  
	
	for( i = 1 ; i <= n ; i++ ) 
	{
		if ( i < pal + L1[pal] ) 
			L1[i] = min( L1[ 2*pal - i ] , pal + L1[pal] - i ) ;
		
		if ( i + L1[i] >= pal + L1[pal] )
		{
			pal = i ;
			
			while (  i - L1[i] >= 1 && i + L1[i] + 1 <= n && v[ i - L1[i] ] == v[ i + L1[i] + 1 ] )
				L1[i]++;
		}
	}
	
	for( i = 1 ; i <= n ; i++ )
		sol += L1[i];
	
	pal = 1 ; 
	
	for( i = 2 ; i <= n ; i++ ) 
	{
		if ( i < pal + L2[pal] ) 
			L2[i] = min( L2[ 2*pal - i ] , pal + L2[pal] - i ) ;
		
		if ( i + L2[i] >= pal + L2[pal] )
		{
			pal = i ;
			
			while (  i - L2[i] - 1 >= 1 && i + L2[i] + 1 <= n && v[ i - L2[i] - 1 ] == v[ i + L2[i] + 1 ] )
				L2[i]++;
		}
	}
	
	for( i = 1 ; i <= n ; i++ )
		sol += L2[i];
	
	printf("%lld",sol);
	
	return 0;
}