Cod sursa(job #2022197)

Utilizator xtreme77Patrick Sava xtreme77 Data 15 septembrie 2017 22:11:28
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
/**
 * Code by Patrick Sava
 * "Spiru Haret" National College of Bucharest
 **/
 
# include "fstream"
# include "cstring"
# include "vector"
# include "queue"
# include "bitset"
# include "algorithm"
# include "map"
# include "set"
# include "unordered_map"
# include "deque"
# include "string"
# include "iomanip"
# include "cmath"
# include "stack"
# include "cassert"
 
const char IN [ ] =  "pscpld.in" ;
const char OUT [ ] = "pscpld.out" ;
 
using namespace std ;
 
# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( register int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( register int a = b ; a >= c ; -- a )
 
ifstream cin ( IN ) ;
ofstream cout ( OUT ) ;
 
const int MAX = 2e6 + 14 ;
 
char sir [ MAX >> 1 ] ;
char M [ MAX ] ;
 
int pali [ MAX ] ;
 
int main()
{
    cin >> ( sir + 1 ) ;
    int l = strlen ( sir + 1 ) ;
    int n = 0 ;
    FORN ( i , 1 , l )
    {
        ++ n ;
        M [ n ] = sir [ i ] ;
        ++ n ;
        M [ n ] = '#' ;
    }
    -- n ;
    int center = 1 ;
    int R = 0 ;
    pali [ 1 ] = 0 ;
    FORN ( i , 1 , n )
    {
        if ( i > center + R ) {
            while ( i - pali [ i ] >= 1 and i + pali [ i ] <= n and M [ i - pali [ i ] ] == M [ i + pali [ i ] ] )
                ++ pali [ i ] ;
        }
        else {
            //int rr = i - center ;
            //int sim = center - rr ;
            int sim = 2 * center - i ;
            //cout << sim << ' ' << pali [ sim ] << '\n' ;
            pali [ i ] = min ( pali [ sim ] , center + R - i ) ;
            while ( i - pali [ i ] >= 1 and i + pali [ i ] <= n and M [ i - pali [ i ] ] == M [ i + pali [ i ] ] ) {
                ++ pali [ i ] ;
				assert (pali [sim] >= center + R - i) ; 
			}
        }
 
        if ( i + pali [ i ] - 1 > center + R ) {
            center = i ;
            R = pali [ i ] - 1 ;
        }
        //cout << pali [ i ] << ' ' ;
    }
    //cout << endl ;
    long long result = 0 ;
    FORN ( i , 1 , n ) {
        if ( M [ i ] != '#' )
            result = result + ( pali [ i ] + 1 ) / 2 ;
        else
            result = result + ( pali [ i ]     ) / 2 ;
        //cout << M [ i ] << ' ' ;
    }
    //cout << endl ;
    cout << result << '\n' ;
    return 0 ;
}