Cod sursa(job #2522489)

Utilizator Alex_AeleneiAlex Aelenei Ioan Alex_Aelenei Data 12 ianuarie 2020 16:48:13
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 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 , dist ;

    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 ] ;

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

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

        pld [ i ] = dist ;
        -- dist ;

        if ( i + dist > mxext )
            last = i ;

        ans += dist / 2 ;
    }

    cout << ans + n / 2 ;

    return 0 ;
}