Cod sursa(job #2942046)

Utilizator TghicaGhica Tudor Tghica Data 18 noiembrie 2022 20:18:11
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int t[2000005];
char s[2000005];

signed main() {
  char ch;
  int i, curCenter, lung;
  long long rez;
  curCenter = 0;
  lung = 0;
  while(cin>>ch) {
    s[lung] = '#';
    lung++;
    s[lung] = ch;
    lung++;
  }
  s[lung] = '#';
  for (i = 1; i <= lung; i++) {
    if (i <= curCenter + t[curCenter]) {
      t[i] = min(t[2 * curCenter - i], curCenter + t[curCenter] - i);
    }
    else {
      t[0] = 0;
    }
    while (i + t[i] + 1 <= lung && i - t[i] - 1 >= 0 && s[i - t[i] - 1] == s[i + t[i] + 1]) {
      t[i]++;
    }
    if (i + t[i] > curCenter + t[curCenter]) {
      curCenter = i;
    }
  }
  rez = 0;
  for (i = 1; i <= lung; i++) {
    if (i % 2 == 1) {
     rez = rez + (long long)t[i] / 2 + 1;
    }
    else {
      rez = rez + (long long)t[i] / 2;
    }
  }
  cout << rez;
  return 0;
}