Cod sursa(job #2799136)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 12 noiembrie 2021 14:35:07
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
#include <cstring>

using namespace std;

const int N = 1e6 + 5;

char s[N];
int d[N], n;
long long ans;

void mnc() {
  int l, r;
  l = 0, r = -1;
  for (int i = 0; i < n; ++i) {
    int k;
    if (i > r) k = 1;
    else k = min(d[l + r - i], r - i + 1);
    while (i - k >= 0 && 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];
  }
  l = 0, r = -1;
  for (int i = 0; i < n; ++i) {
    int k;
    if (i > r) k = 0;
    else k = min(d[l + r - i + 1], r - i + 1);
    while (i - k - 1 >= 0 && 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];
  }
}

int main() {
  ifstream cin("pscpld.in");
  ofstream cout("pscpld.out");
  cin >> s;
  n = strlen(s);
  cin.close();
  mnc();
  cout << ans << "\n";
  cout.close();
  return 0;
}