Cod sursa(job #2864046)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 7 martie 2022 15:32:26
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <bits/stdc++.h>

using namespace std;

void manacher(const string& s, vector<int>& z) {
  int l = 0, r = -1;
  z[0] = 0;
  for (int i = 1; i < s.size(); ++i) {
    z[i] = 0;
    if (i <= r)
      z[i] = min(z[l + (r - i)], r - i + 1);
    while (i + z[i] < s.size() && i - z[i] >= 0 && s[i + z[i]] == s[i - z[i]])
      ++z[i];
    if (i + z[i] - 1 > r) {
      l = i - z[i] + 1;
      r = i + z[i] - 1;
    }
  }
}

int main() {
  ifstream cin("pscpld.in");
  ofstream cout("pscpld.out");
  string a;
  cin >> a;
  cin.close();
  string s = "#";
  for (int i = 0; i < a.size(); ++i) {
    s.push_back(a[i]);
    s.push_back('#');
  }
  vector<int> z(s.size());
  manacher(s, z);
  long long ans = 0;
  for (auto i: z)
    ans += i / 2;
  cout << ans << "\n";
  cout.close();
  return 0;
}