Cod sursa(job #2522453)

Utilizator Alex_AeleneiAlex Aelenei Ioan Alex_Aelenei Data 12 ianuarie 2020 16:03:44
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std ;

const int NMAX = 1e6 ;
char str [ NMAX + 5 ] ;
char str1 [ 2 * NMAX + 5 ] ;
int pld [ 2 * NMAX + 5 ] ;

int main ()
{
    FILE * f ;
    f = fopen ( "pscpld.in" , "r" ) ;
    freopen ( "pscpld.out" , "w" , stdout ) ;

    int n , i , last = 0 , mxext = 0 , cnt , ans = 0  ;

    fread ( str , 1 , NMAX , f ) ;
    n = strlen ( str ) ; -- n ;

    for ( i = 0 ; i <= n ; ++ i )
        str1 [ 2 * i + 1 ] = str [ i ] , str1 [ 2 * i ] = 0 ;

    for ( i = 1 ; i < 2 * n ; ++ i )
    {
        mxext = last + pld [ last ] ;

        if ( i <= mxext )
            pld [ i ] = min ( pld [ last - ( i - last ) ] , mxext - i ) ;

        while ( i + pld [ i ] < 2 * n && i - pld [ i ] >= 1 && str1 [ i + pld [ i ] ] == str1 [ i - pld [ i ] ] )
            ++ pld [ i ] ;

        -- pld [ i ] ;
        if ( pld [ i ] && str1 [ i + pld [ i ] ] == 0 )
            -- pld [ i ] ;

        if ( i + pld [ i ] > mxext )
            last = i ;
    }

    for ( i = 1 ; i < 2 * n ; ++ i )
    {
        /*if ( str1 [ i ] == 0 )
            str1 [ i ] = '*' ;
        printf ( "%2d : %d %c\n" , i , pld [ i ] , str1 [ i ] ) ;*/
        ans += ( pld [ i ] + 1 ) / 2 ;
    }

    printf ( "%d" , ans + n ) ;

    return 0 ;
}