Pagini recente » Cod sursa (job #444983) | Cod sursa (job #1761615) | Cod sursa (job #2009209) | Cod sursa (job #574087) | Cod sursa (job #1979980)
# 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;
}