Cod sursa(job #2261486)

Utilizator DysKodeTurturica Razvan DysKode Data 16 octombrie 2018 11:47:34
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#include <cstring>
#include <iostream>

using namespace std;

char c[1000010], s[2000010];
int i,j,n,m,k,p,best[2000010],bst,ans,sim;

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

int expand( int poz , int off = 0 ){
	int i,j;
	for( i = poz - off , j = poz + off ; i >= 0 && j < n ; j++ , i-- ){
		if( s[ i ] != s[ j ] )
			break;
	}
	return j - poz;
}

int main(){

	fin.get( c , 1000010 );
	n = strlen( c );
	for( int i = 0 ; i < n ; i++ ){
		s[ 2 * i ] = '*';
		s[ 2 * i + 1 ] = c[ i ];
	}

	n = 2 * n;
	best[0] = 1;
	bst = 0;

	//cout<<"* 1\n";

	for( int i = 1 ; i < n ; i++ ){
        //cout << bst << ' ' << best[ bst ] << '\n';
		if( i >= bst + best[ bst ] ){
			bst = i;
			best[ i ] = expand( i );
		} else {
			int sim = bst - ( i - bst );
			best[ i ] = min( best[ sim ] , bst + best[ bst ] - i );
			best[ i ] = expand( i , best[ i ] - 1 );
		}
		ans = ans + ( best[ i ] + 1 ) / 2;
		//cout << s[ i ] << ' ' << ' ' << ' ' << best[ i ] << '\n';
	}
	fout << ans - n / 2 + 1;

return 0;
}