Cod sursa(job #2522402)

Utilizator Alex_AeleneiAlex Aelenei Ioan Alex_Aelenei Data 12 ianuarie 2020 15:01:00
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std ;

const int NMAX = 1e3 ;
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 = 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 ] + 1 <= 2 * n && i - pld [ i ] - 1 >= 1 && str1 [ i + pld [ i ] + 1 ] == str1 [ i - pld [ i ] - 1 ] )
            ++ pld [ i ] ;

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

    int ans = n ;

    for ( i = 1 ; i <= 2 * n ; ++ i )
        ans += pld [ i ] / 2 ;

    printf ( "%d" , ans ) ;

    return 0 ;
}