Cod sursa(job #1979980)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 11 mai 2017 20:45:29
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
# include <cstdio>
# include <cstdlib>

using namespace std;

const int MAX_LEN = 2000005;

char s[MAX_LEN];
int hash_l[MAX_LEN], hash_r[MAX_LEN];
int sigma_power[MAX_LEN];

const long long sigma = 31LL;
const int MOD = 10000007;

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 ++] = 'z' + 1;
        s[n ++] = ch;
        ch = fgetc( fin );
    }

    s[n ++] = 'z' + 1;

    sigma_power[0] = 1;
    for ( int i = 1; i <= n; i ++ )
        sigma_power[i] = sigma_power[i - 1] * sigma % MOD;
    for ( int i = 1; i < n; i ++ )
        hash_l[i] = ( hash_l[i - 1] + ( s[i] - 'a' + 1 ) * sigma_power[i - 1] ) % MOD;
    for ( int i = n - 1; i > 0; i -- )
        hash_r[i] = ( hash_r[i + 1] + ( s[i] - 'a' + 1 ) * sigma_power[n - i - 1] ) % MOD;


    long long k = 0;
    for ( int i = 1; i < n; i ++ ) {
        int t = 0;
        for ( int pas = ( 1 << 21 ); pas > 0; pas >>= 1 )
            if ( i - t - pas >= 0 && i + t + pas <= n &&
                 (long long) ( hash_l[i] - hash_l[i - t - pas] + MOD ) % MOD * sigma_power[n - (i - t - pas)] % MOD ==
                 (long long) ( hash_r[i] - hash_r[i + t + pas] + MOD ) % MOD * sigma_power[( i + t + pas)] % MOD )
                t += pas;
        k += t / 2;
    }

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

    fclose( fin );
    fclose( fout );


    return 0;
}