Pagini recente » Cod sursa (job #2386472) | Cod sursa (job #1269934) | Cod sursa (job #167235) | Cod sursa (job #2449306) | Cod sursa (job #1979994)
# include <cstdio>
# include <cstdlib>
using namespace std;
const int MAX_N = 2000005;
char s[MAX_N];
const int MOD = 1000000007;
const long long sigma = 31;
int spow[MAX_N];
int hl[MAX_N], hr[MAX_N];
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;
spow[0] = 1;
for ( int i = 1; i <= n; i ++ )
spow[i] = spow[i - 1] * sigma % MOD;
for ( int i = 1; i < n; i ++ )
hl[i] = ( hl[i - 1] + spow[i - 1] * ( s[i] - 'a' + 1LL ) ) % MOD;
for ( int i = n - 1; i > 0; i -- )
hr[i] = ( hr[i + 1] + spow[n - i - 1] * ( s[i] - 'a' + 1LL ) ) % 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 ) ( ( hl[i] - hl[i - t - pas] + MOD ) % MOD ) * spow[n - (i - t - pas)] % MOD ==
( long long ) ( ( hr[i] - hr[i + t + pas] + MOD ) % MOD ) * spow[i + t + pas] % MOD )
t += pas;
k += t / 2;
}
fprintf( fout, "%lld", k );
fclose( fin );
fclose( fout );
return 0;
}