Cod sursa(job #2857999)

Utilizator vlad2009Vlad Tutunaru vlad2009 Data 26 februarie 2022 19:43:11
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <fstream>

const int MAX_N = 1e6;
const int B = 257;
const int P = 1e9 + 7;
int prefH[1 + MAX_N], prefrevH[1 + MAX_N], power[1 + MAX_N];

int rangeHash(int l, int r) {
  return (prefH[r] - (long long)prefH[l - 1] * power[r - l + 1] % P + B) % P;
}

int rangerevHash(int l, int r) {
  return (prefrevH[l] - (long long)prefrevH[r + 1] * power[r - l + 1] % P + B) % P;
}

int cb_imp(int n, int pos) {
  int st = 0, dr = (n - pos) / 2 , sol = -1;
  while (st <= dr) {
    int mijl = (st + dr) / 2;
    if (rangeHash(pos - mijl, pos + mijl) == rangerevHash(pos - mijl, pos + mijl)) {
      sol = mijl;
      st = mijl + 1;
    } else {
      dr = mijl - 1;
    }
  }
  return sol + 1;
}

int cb_par(int n, int pos) {
  int st = 0, dr = (n - pos + 1) / 2, sol = 0;
  while (st <= dr) {
    int mijl = (st + dr) / 2;
    if (rangeHash(pos - mijl + 1, pos + mijl) == rangerevHash(pos - mijl + 1, pos + mijl)) {
      sol = mijl;
      st = mijl + 1;
    } else {
      dr = mijl - 1;
    }
  }
  return sol;
}

int cb(int n, int pos) {
  return cb_imp(n, pos) + cb_par(n, pos);
}

int main() {
  std::ifstream fin("pscpld.in");
  std::ofstream fout("pscpld.out");
  std::string s;
  fin >> s;
  int n = s.size();
  for (int i = 1; i <= n; i++) {
    prefH[i] = ((long long)prefH[i - 1] * B + (int)s[i - 1]) % P;
  }
  for (int i = n; i >= 1; i--) {
    prefrevH[i] = ((long long)prefrevH[i + 1] * B + (int)s[i - 1]) % P;
  }
  power[0] = 1;
  for (int i = 1; i <= MAX_N; i++) {
    power[i] = (long long)power[i - 1] * B % P;
  }
  int answer = 0;
  for (int i = 1; i <= n; i++) {
    answer += cb(n, i);
  }
  fout << answer;
  return 0;
}