Cod sursa(job #1279134)

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

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

  return 0;
}