Cod sursa(job #1279149)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 29 noiembrie 2014 20:40:16
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 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]++;
    }
    for (li = i - 1, lf = i + 1; li >= i - o[i] + 1; li--, lf++) {
      o[lf] =
          std::max(o[lf],
                   std::min(o[li], std::min(i - li + 1, li - (i - 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]++;
    }
    total += o[i] + e[i];
  }

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

  return 0;
}