Pagini recente » Cod sursa (job #2524370) | Cod sursa (job #1542662) | Cod sursa (job #2962081) | Cod sursa (job #3277797) | Cod sursa (job #2877557)
// This program was written on 24.03.2022
// for problem pscpld
// by Mircea Rebengiuc
// aplicatie manaher
#include <stdio.h>
#include <ctype.h>
#define MAXN 1000000
char str[2 * MAXN + 1];
int r[2 * MAXN + 1];// 'raza' palindromului maxima
static inline int min( int a, int b ){
return a < b ? a : b;
}
int main(){
FILE *fin = fopen( "pscpld.in", "r" );
FILE *fout = fopen( "pscpld.out", "w" );
int n, i = 0, ch, c, sum;
str[i++] = '+';
while( isalpha( ch = fgetc( fin ) ) ){
str[i++] = ch;
str[i++] = '.';
}
str[i - 1] = '-';
n = i - 2;
r[c = 0] = 1;
for( i = 1 ; i <= n ; i++ ){
// calculam raza de la care incepem
if( c + r[c] > i )
r[i] = min( r[2 * c - i], c + r[c] - i );
else
r[i] = 1;
while( str[i - r[i]] == str[i + r[i]] )
r[i]++;
if( i + r[i] > c + r[c] )
c = i;
}
//for( i = 0 ; i < n + 2 ; i++ )
// fputc( str[i], stdout );
//fputc( '\n', stdout );
//for( i = 0 ; i < n + 2 ; i++ )
// printf( "%d", r[i] );
//fputc( '\n', stdout );
sum = 0;
for( i = 1 ; i <= n ; i++ )
sum += ((r[i] + (i & 1)) >> 1);
fprintf( fout, "%d\n", sum );
fclose( fin );
fclose( fout );
return 0;
}