Cod sursa(job #3288674)

Utilizator AsandeiStefanAsandei Stefan-Alexandru AsandeiStefan Data 23 martie 2025 15:59:38
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <string>

using namespace std;

const int nmax = 1e6;

ifstream fin("pscpld.in");
ofstream fout("pscpld.out");

uint64_t manacher[2 * nmax + 1], middle, ans;
string t, s;

int main() {
  fin >> t;

  // doar palindroame impare
  for (int i = 0; i < t.size(); i++) {
    s += '#';
    s += t[i];
  }
  s += '#';

  // construim manacher[]
  middle = -1;
  for (int i = 0; i < s.size(); i++) {
    // daca putem lua din spate
    if (middle != -1 && middle + manacher[middle] - 1 >= i) {
      manacher[i] =
          min(manacher[middle - (i - middle)], middle + manacher[middle] - i);
    }

    // brut
    while (i + manacher[i] < s.size() && i - manacher[i] >= 0 &&
           s[i + manacher[i]] == s[i - manacher[i]]) {
      manacher[i]++;
    }

    // actualizam
    if (middle == -1 || i + manacher[i] > middle + manacher[middle]) {
      middle = i;
    }
  }

  for (int i = 0; i < s.size(); i++) {
    ans += manacher[i] / 2;
  }
  fout << ans << '\n';
  return 0;
}

/*
Numarati subsecventele palindrom pe care sirul de caractere le contine.

https://www.infoarena.ro/problema/pscpld
*/