Cod sursa(job #2738935)

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

using namespace std;
using int64 = long long;

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

const int NMAX = 1e6;
int dp[NMAX][2], l[2], r[2];

void solve() {
  string s;
  fin >> s;
  int N = s.size();
  int64 ans = 0;
  r[0] = r[1] = -1;
  for (int i = 0; i < N; ++i)
    for (int par = 0; par < 2; ++par) {
      int flag = !par;
      int k = (i > r[par]) ? par : min(dp[l[par] + r[par] + flag - i][par], r[par] - i + 1);
      while (0 <= i - k - flag && i + k < N && s[i - k - flag] == s[i + k])
        ++k;
      ans += k;
      dp[i][par] = k--;
      if (i + k > r[par]) {
        l[par] = i - k - flag;
        r[par] = i + k;
      }
    }
  fout << ans << '\n';
}

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

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