Cod sursa(job #2036597)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 10 octombrie 2017 20:40:10
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

const long long BASE = 227;
const long long MOD = 77007001;

void Make(string &in_str, string &s) {

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

void Init(string &s, vector < long long > &Hash_st, vector < long long > &Hash_dr,
  vector < long long > &Base_pow) {

  for (int i = 0; i < s.size(); i ++) {
    if (not i) {
      Hash_st[0] = 1ll * s[0];
      continue;
    }

    Hash_st[i] = (Hash_st[i - 1] * BASE + 1ll * s[i]) % MOD;
  }

  for (int i = s.size() - 1; i >= 0; i --) {
    if (i == s.size() - 1) {
      Hash_dr[i] = 1ll * s[s.size() - 1];
      continue;
    }

    Hash_dr[i] = (Hash_dr[i + 1] * BASE + 1ll * s[i]) % MOD;
  }

  Base_pow[0] = 1ll;
  for (int i = 1; i <= s.size(); i ++) {
    Base_pow[i] = (Base_pow[i - 1] * BASE) % MOD;
  }
}

void poz(long long &x) {
  if (x < 0) {
    x += MOD;
  }
}

void Solve(vector < long long > &Hash_st, vector < long long > &Hash_dr,
  vector < long long > &Base_pow, vector < int > &how_many, string &s) {

  int len = s.size();
  for (int i = 0; i < len; i ++) {
    if (i == 0 or i == len - 1) {
      how_many[i] = (s[i] == '$' ? 0 : 1);
      continue;
    }    

    int ans = 0;
    int left = 0;
    int right = min(len - i - 1, i);
    while (left <= right) {
      int cur_len = (left + right) >> 1;
      
      long long l_H = Hash_st[i - 1];
      if (i > cur_len) {
        l_H -= (Hash_st[i - 1 - cur_len] * Base_pow[cur_len]) % MOD; 
      } 
      long long r_H = Hash_dr[i + 1] - ((Hash_dr[i + 1 + cur_len] * Base_pow[cur_len]) % MOD);
      
      poz(r_H);
      poz(l_H);

      if (l_H == r_H) {
        ans = cur_len;
        left = cur_len + 1;
        continue;
      } 

      right = cur_len - 1;
    }

    if (i % 2 == 0) {
      how_many[i] = 1 + ans / 2;
    }    
    else {
      how_many[i] = (ans + 1) / 2;
    }
  }
}

int main() {

  string in_str, s;
  cin >> in_str;
  Make(in_str, s);

  vector < long long > Hash_st(s.size() + 7);
  vector < long long > Hash_dr(s.size() + 7);
  vector < long long > Base_pow(s.size() + 7);
  Init(s, Hash_st, Hash_dr, Base_pow);

  vector < int > how_many(s.size() + 7);
  Solve(Hash_st, Hash_dr, Base_pow, how_many, s);

  long long sol = 0;
  for (int i = 0; i < s.size(); i ++) {
    sol += 1ll * how_many[i];
  }

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