Cod sursa(job #1979589)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 10 mai 2017 21:38:36
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
# include <cstdio>
# include <cstdlib>

using namespace std;

static int min( const int& a, const int& b ) {
    return a < b ? a : b;
}

const int MAX_LEN = 1000000;
char s[2 * MAX_LEN + 5];
int h[2 * MAX_LEN + 5];

int main() {
    FILE *fin = fopen( "pscpld.in", "r" ), *fout = fopen( "pscpld.out", "w" );

    int n = 1;
    char ch = fgetc( fin );

    while ( ch != '\n' ) {
        s[n ++] = '#';
        s[n ++] = ch;
        ch = fgetc( fin );
    }
    s[n ++] = '#';
    s[0] = '@';
    s[n] = '%';

    long long k = 0;
    int c = 0, r = 0;

    for ( int i = 1; i < n; i ++ ) {
        int t = 0;
        if ( i <= r )
            t = min( h[2 * c - i], r - i );

        while ( s[i + t + 1] == s[i - t - 1] )
            t ++;

        if ( i + t > r ) {
            c = i;
            r = i + t;
        }

        h[i] = t;
        k += ( t + 1 ) / 2;
    }

    fprintf( fout, "%lld", k );

    fclose( fin );
    fclose( fout );

    return 0;
}