Cod sursa(job #2877557)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 24 martie 2022 22:14:27
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
// 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;
}