[Codemarshal] C. Votka and String

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : C. Votka and String
Source            : Codemarshal
                    Eid Punormiloni Contest 2016
Category          : String, Data Structure
Algorithm         : Hashing, Binary Indexed Tree
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define int         long long int  
#define endl       '\n'  
  
static const int maxn = 2e5 + 5;  
static const int mod = 1e9 + 123;  
  
int gen_base(const int before, const int after)  
{  
      auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();  
      mt19937 mt_rand(seed);  
      int base = uniform_int_distribution <int> (before, after)(mt_rand);  
      return base % 2 == 0 ? base - 1 : base;  
}  
  
long long pow1[maxn];  
unsigned long long pow2[maxn];  
int base;  
  
void preCalc()  
{  
      assert(base < mod);  
      pow1[0] = 1;  
      pow2[0] = 1;  
      for (int i = 1; i < maxn; i++)  
      {  
            pow1[i] = (1LL * pow1[i - 1] * base) % mod;  
            pow2[i] = (pow2[i - 1] * base);  
      }  
}  
  
struct Hash  
{  
      vector <long long> pref1;  
      vector <unsigned long long> pref2;  
      Hash() {}  
      Hash(const string &s) : pref1(s.size() + 1u, 0), pref2(s.size() + 1u, 0)  
      {  
            assert(base < mod);  
            int n = s.size();  
            for (int i = 0; i < n; i++)  
            {  
                  assert(base > s[i]);  
                  pref1[i + 1] = (pref1[i] + 1LL * s[i] * pow1[i]) % mod;  
                  pref2[i + 1] = pref2[i] + s[i] * pow2[i];  
            }  
      }  
      pair <long long, unsigned long long> getHash(const int pos, const int len, const int mxPow = 0)  
      {  
            long long hash1 = pref1[pos + len] - pref1[pos];  
            unsigned long long hash2 = pref2[pos + len] - pref2[pos];  
            if (hash1 < 0) hash1 += mod;  
            if (mxPow != 0)  
            {  
                  hash1 = 1LL * hash1 * pow1[mxPow - (pos + len - 1)] % mod;  
                  hash2 = hash2 * pow2[mxPow - (pos + len - 1)];  
            }  
            return make_pair(hash1, hash2);  
      }  
};  
  
  
int Tree[maxn];  
int N;  
  
void update(int pos, int val)  
{  
      while (pos <= N)  
      {  
            Tree[pos] += val;  
            pos += (pos & -pos);  
      }  
}  
  
void range_update(int l, int r, int val)  
{  
      update(l, val);  
      update(r + 1, -val);  
}  
  
int query(int pos)  
{  
      int sum = 0;  
      while (pos > 0)  
      {  
            sum += Tree[pos];  
            pos -= (pos & -pos);  
      }  
      return sum;  
}  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
//      #ifndef ONLINE_JUDGE  
//            freopen("in.txt", "r", stdin);  
//      #endif // ONLINE_JUDGE  
  
      base = gen_base(256, mod);  
      preCalc();  
  
      int tc;  
      cin >> tc;  
      for (int tcase = 1; tcase <= tc; tcase++)  
      {  
            string s;  
            cin >> s;  
            int n;  
            cin >> n;  
            vector <int> queries(n);  
            for (int &x : queries) cin >> x;  
            Hash hash_s(s);  
            int len = s.size();  
            N = len;  
            int mxPow = len;  
            for (int i = 1; i < len; i++)  
            {  
                  pair <long long, unsigned long long> hashPrefix;  
                  pair <long long, unsigned long long> hashSuffix;  
                  int lo = i;  
                  int hi = len - 1;  
                  int id = -1;  
                  while (lo <= hi)  
                  {  
                        int mid = lo + hi >> 1;  
                        int prefixLength = mid - i + 1;  
                        hashPrefix = hash_s.getHash(0, prefixLength, mxPow);  
                        hashSuffix = hash_s.getHash(i, prefixLength, mxPow);  
                        if (hashPrefix == hashSuffix) id = mid, lo = mid + 1;  
                        else hi = mid - 1;  
                  }  
                  if (id == -1) continue;  
                  int validLen = id - i + 1;  
                  range_update(1, validLen, 1);  
            }  
            for (int i = 0; i < n; i++)  
            {  
                  int x = queries[i];  
                  int ans;  
                  if (x == 0) ans = len;  
                  else ans = query(x) + (x <= len);  
                  cout << ans << " \n"[i + 1 == n];  
            }  
            fill(begin(Tree), end(Tree), 0);  
      }  
}