Cod sursa(job #1050204)

Utilizator superman_01Avramescu Cristian superman_01 Data 8 decembrie 2013 12:58:31
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>

#define get_min(a,b) ((a)<(b)?(a):(b))
#define MAX_SIZE 1000005

using namespace std;

ifstream in ( "pscpld.in" );
ofstream out ( "pscpld.out" );

char sir[MAX_SIZE];
int DP[2][MAX_SIZE] , N ;
long long Sol ;

int Expand ( int Left , int Right )
{
	int len = 0 ;
    for ( ;Left > 0 and Right <= N and sir[Left] == sir[Right]; ++len , ++Right , --Left );
		
    return len;	
}

void ManacherUnEven ( void )
{
	int i , j , P = 0 , R = 0;
	for ( i = 1 ; i <= N ; ++i )
	{
		int Left , Right ;
		if ( R >= i )
		{
			DP[0][i] = get_min ( DP[0][ P - ( i-P) ]  , R -i );
		}
		Left = i - DP[0][i];
		Right = i + DP[0][i];
		DP[0][i] = Expand ( Left , Right );
		if ( i + DP[0][i] > R )
		{
			P = i ;
			R = i + DP[0][i];
		}
		Sol += ( long long) DP[0][i];
	}
	
}

void ManacherEven ( void )
{
		int i , j , P = 0 , R = 0;
	for ( i = 1 ; i <= N ; ++i )
	{
		int Left , Right ;
		if ( sir[i] != sir[i+1] ) continue;
		if ( R > i )
		{
			DP[1][i] = get_min ( DP[1][ P - ( i-P) ]  , R -i -1 );
		}
		Left = i - DP[1][i];
		Right = i + DP[1][i];
		DP[1][i] = Expand ( Left , Right );
		if ( i + 1 + DP[1][i] > R )
		{
			P = i ;
			R = i + 1 +  DP[1][i];
		}
		Sol += ( long long) DP[1][i];
	}
}
int main ( void )
{
	in >> ( sir + 1 );
	sir[0] = ' ';
	N = strlen(sir) - 1;
	ManacherEven();
	ManacherUnEven();
	out << Sol << "\n";
	in.close();
	out.close();
	return 0;
}