Cod sursa(job #2738927)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 6 aprilie 2021 15:58:32
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <bits/stdc++.h>

using namespace std;
using int64 = long long;

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

void solve() {
  string s;
  fin >> s;
  int N = s.size();
  vector<int> d(N);
  int64 ans = 0;
  for (int i = 0, l = 0, r = -1; i < N; ++i) { /// lungimi impare
    int k = (i > r) ? 1 : min(d[l + r - i], r - i + 1);
    while (0 <= i - k && i + k < N && s[i - k] == s[i + k])
      ++k;
    d[i] = k--;
    if (i + k > r)
      l = i - k, r = i + k;
    ans += d[i];
  }
  d = vector<int>(N);
  for (int i = 0, l = 0, r = -1; i < N; ++i) { /// lungimi pare
    int k = (i > r) ? 0 : min(d[l + r - i + 1], r - i + 1);
    while (0 <= i - k - 1 && i + k < N && s[i - k - 1] == s[i + k])
      ++k;
    d[i] = k--;
    if (i + k > r)
      l = i - k - 1, r = i + k;
    ans += d[i];
  }
  fout << ans << '\n';
}

void close_files() {
  fin.close();
  fout.close();
}

int main() {
  solve();
  close_files();
  return 0;
}