Cod sursa(job #1315158)

Utilizator xtreme77Patrick Sava xtreme77 Data 12 ianuarie 2015 16:04:40
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
/*
 * Code by Spiromanul
 */


#include <fstream>
#include <cstring>

const char IN [ ] = "pscpld.in" ;
const char OUT [ ] = "pscpld.out" ;
const int MAX = 1110111 ;

using namespace std;

ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;

char sir [ MAX << 1 ] ;
char S [ MAX ] ;
int pali [ MAX << 1 ] , n ;

int main (    )
{
    fin >> ( S + 1 ) ;
    int l = strlen ( S + 1 )  ;
    sir [ n ] = '$' ;
    for ( int i = 1 ; i <= l ; ++ i )
    {
        ++ n ;
        sir [ n ] = S [ i ] ;
        ++ n ;
        sir [ n ] = '$' ;
    }
    sir [ n + 1 ] = '@' ;
    pali [ 0 ] = 1 ;
    pali [ 1 ] = 1 ;
    int centru = 1 ;
    int R = 1 ;
    for ( int i = 2 ; i < n ; ++ i )
    {
        pali [ i ] = ( R > i ) ? min ( pali [ 2 * centru - i ] , R - i ) : 0 ;
        while ( sir [ i - pali [ i ] - 1 ] == sir [ i + pali [ i ] + 1 ] )
            ++ pali [ i ] ;
        if ( i + pali [ i ] > R )
        {
            R = i + pali [ i ] ;
            centru = i ;
        }
    }
    long long CET = 0 ;
    for ( int i = 1 ; i <= n ; ++ i )
        CET += ( long long ) ( pali [ i ] + 1 ) >> 1 ;
    fout << CET << '\n' ;
    return 0;
}