Cod sursa(job #2522468)

Utilizator Alex_AeleneiAlex Aelenei Ioan Alex_Aelenei Data 12 ianuarie 2020 16:21:38
Problema PScPld Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std ;

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

int main ()
{
    ifstream cin ( "pscpld.in" ) ;
    ofstream cout ( "pscpld.out" ) ;

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

    cin >> str ;
    n = strlen ( str ) ;

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

    n *= 2 ;

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

        if ( i <= mxext )
        {
            if ( pld [ 2 * last - i ] < mxext - i )
                pld [ i ] = pld [ 2 * last - i ] ;
            else
                pld [ i ] = mxext - i ;
        }

        while ( i + pld [ i ] < 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 ;

        ans += ( pld [ i ] + 1 ) / 2 ;
    }

    cout << ans + n / 2 ;

    return 0 ;
}