Cod sursa(job #2338073)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 6 februarie 2019 22:42:52
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
// By Stefan Radu

#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <string>
#include <cctype>
#include <queue>
#include <deque>
#include <cmath>
#include <stack>
#include <map>
#include <set>

using namespace std;

#define sz(x) (int)(x).size()

typedef pair < int, int > pii;
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

ifstream cin ("pscpld.in");
ofstream cout ("pscpld.out");

int main() {

  string a, s = " ";
  cin >> a;

  for (auto x : a) {
    s += x, s += '#';
  }

  vector < int > dp(sz(s) + 7);

  int o = 0, r = 0;
  for (int i = 1; i < sz (s); ++ i) {

    if (i >= r) {
      o = i;
      while (s[i + dp[i]] == s[i - dp[i]]) {
        if (i - (++ dp[i]) <= 0) {
          -- dp[i];
          break;
        }
      }

      if (s[i + dp[i]] != s[i - dp[i]]) -- dp[i];

      r = i + dp[i];
      continue;
    }

    int op = 2 * o - i;

    if (i + dp[op] < r) {
      dp[i] = dp[op];
      continue;
    }

    dp[i] = r - i;
    while (i - dp[i] >= 1 and s[i + dp[i]] == s[i - dp[i]]) {
      if (i - (++ dp[i]) == 0) {
        -- dp[i];
        break;
      }
    }

    if (s[i + dp[i]] != s[i - dp[i]]) -- dp[i];

    r = i + dp[i];
    o = i;
  }

  ll ans = 0;
  for (int i = 1; i < sz(s); ++ i) {
    if (i & 1) {
      ans += dp[i] / 2 + 1;
    }
    else {
      ans += (dp[i] + 1) / 2;
    }
  }

  cout << ans << '\n';
}