Pagini recente » Cod sursa (job #2260387) | Cod sursa (job #3122358) | Cod sursa (job #1327766) | Cod sursa (job #2352644) | Cod sursa (job #1979583)
# include <cstdio>
# include <cstdlib>
using namespace std;
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 = h[2 * c - 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;
}