Cod sursa(job #2037011)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 11 octombrie 2017 16:08:51
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <fstream>
#include <vector>
#include <string>

using namespace std;

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

void Make(string &s, string in_str) {

  for (auto x : in_str) {
    s += x;
    s += '$';
  }
}

bool is_good(int cnt, int i, int len) {
  return i + cnt < len and i - cnt >= 0;
}

void Solve(string s, vector < int > &pali, int &poz, int &max_r) {

  int len = s.size();
  for (int i = 0; i < len; i ++) {
    if (i >= max_r) {
      int cnt = 0;
      while (is_good(cnt, i, len)) {
        if (s[i + cnt] == s[i - cnt]) {
          cnt ++;
          continue;
        }
        break;
      }

      cnt -= 1;
      pali[i] = cnt;
      max_r = i + cnt;
      poz = i;
      continue;
    }

    int k = pali[2 * poz - i];
    if (i + k < max_r) {
      pali[i] = pali[2 * poz - i];
      continue;
    }
    
    int cnt = max_r - i + 1;
    while (is_good(cnt, i, len)) {
      if (s[i + cnt] == s[i - cnt]) {
        cnt ++;
        continue;
      }
      break;
    }

    cnt -= 1;
    if (cnt) {
      pali[i] = cnt;
      max_r = i + pali[i];
      poz = i;
    }
  }

  for (int i = 0; i < len; i ++) {
    if (i % 2 == 0) {
      pali[i] = 1 + pali[i] / 2;
    }
    else {
      pali[i] = (pali[i] + 1) / 2;
    }
  }
}

int main(int argc, char const *argv[]) {
  
  string in_str, s;
  cin >> in_str;
  Make(s, in_str);

  vector < int > pali(s.size() + 7);
  int poz = -1, max_r = -1;
  Solve(s, pali, poz, max_r);

  int sol = 0;
  for (int i = 0; i < s.size(); i ++) {
    sol += pali[i];
  }

  cout << sol << '\n';
}