Cod sursa(job #1279140)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 29 noiembrie 2014 20:29:13
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <iostream>
#include <fstream>
#include <cstring>

char s[1000010];
int  o[1000010];
int  e[1000010];

int main()
{
  FILE* f = fopen("pscpld.in", "r");
  std::ofstream out("pscpld.out");

  fscanf(f, "%s", &s[1]);
  int n = strlen(s + 1), li, lf;
  unsigned long long total = 0;
  for (int i = 1; i <= n; ++i) o[i] = 1, e[i] = 0;
  for (int i = 1; i <= n; ++i) {
    // Odd palindome centered in "i".
    for (li = i - o[i], lf = i + o[i];
         li >= 1 && lf <= n && s[li] == s[lf];
         li--, lf++) {
      o[i] ++;
    }
    // Even palindrome seeded between "i - 1" and "i".
    for (li = i - e[i] - 1, lf = i + e[i];
         li >= 1 && lf <= n && s[li] == s[lf];
         li--, lf++) {
      e[i] += 1;
    }
    total += o[i] + e[i];
  }

  fclose(f);
  out << total << std::endl;
  out.close();

  return 0;
}