Cod sursa(job #1978229)

Utilizator TincaMateiTinca Matei TincaMatei Data 7 mai 2017 10:26:35
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <cstdio>
#include <ctype.h>

const int MAX_N = 1000000;
const int BUFF = 4096;
char sir[2*MAX_N+1];
int plm[2*MAX_N+1];
char buff[BUFF];
int curs = BUFF - 1;

inline char getch(FILE *fin) {
  curs++;
  if(curs == BUFF) {
    curs = 0;
    fread(buff, 1, BUFF, fin);
  }
  return buff[curs];
}

int main() {
  int n, n2, left, mid, right;
  long long rez = 1LL;
  char ch;
  FILE *fin = fopen("pscpld.in", "r");
  ch = getch(fin);
  n = 0;
  while(ch != EOF && ch != '\n' && ch != 0) {
    if(isalpha(ch)) {
      sir[2 * n] = ch;
      ++n;
    }
    ch = getch(fin);
  }
  fclose(fin);

  n2 = 2 * n + 1;
  plm[0] = 0;
  left = mid = right = 0;
  for(int i = 1; i < n2; ++i) {
    if(i > right) { //iese rau in afara
      plm[i] = 0;
      mid = left = right = i;
      while(left - 1 >= 0 && right + 1 < n2 && sir[left - 1] == sir[right + 1]) {
        --left;
        ++right;
        ++plm[i];
      }
    } else {
      plm[i] = plm[mid - (i - mid)];
      if(i + plm[i] >= right) {
        plm[i] = right - i;
        mid = i;
        left = i - (right - mid);
        while(left - 1 >= 0 && right + 1 < n2 && sir[left - 1] == sir[right + 1]) {
          --left;
          ++right;
          ++plm[i];
        }
      }
    }

    if(sir[i] == 0)
      rez = rez + (plm[i] + 1) / 2;
    else
      rez = rez + plm[i] / 2 + 1;
  }

  FILE *fout = fopen("pscpld.out", "w");
  fprintf(fout, "%lld", rez);
  fclose(fout);
  return 0;
}