Cod sursa(job #2942019)

Utilizator TghicaGhica Tudor Tghica Data 18 noiembrie 2022 19:09:54
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>

using namespace std;

ifstream cin("pscpld.in");
ofstream cout("pscpld.out");

int t[2000001];

signed main() {
  string basic, s;
  int i, drmax, curCenter, lung, st, dr, rez;
  drmax = 0;
  curCenter = 0;
  cin >> basic;
  for (i = 0; i < basic.size(); i++) {
    s = s + '#' + basic[i];
  }
  lung = s.size() - 1;
  for (i = 1; i <= lung; i++) {
    if (i <= drmax) {
      st = i - t[curCenter - (i - curCenter)];
      dr = i + t[curCenter - (i - curCenter)];
    }
    else {
      st = i;
      dr = i;
    }
    while (dr + 1 <= lung && st - 1 >= 1 && s[st - 1] == s[dr + 1]) {
      st--;
      dr++;
    }
    t[i] = dr - i;
    if (dr > drmax) {
      drmax = dr;
      curCenter = i;
    }
  }
  rez = 0;
  for (i = 1; i <= lung; i++) {
    if (i % 2 == 1) {
     rez = rez + t[i] / 2 + 1;
    }
    else {
      rez = rez + (t[i] + 1) / 2;
    }
  }
  cout << rez;
  return 0;
}