Pagini recente » Cod sursa (job #1912427) | Cod sursa (job #726121) | Cod sursa (job #1388) | Cod sursa (job #488961) | Cod sursa (job #1979585)
# 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 = 100000;
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 ++] = '#';
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;
}