[Gym] J - Non Super Boring Substring

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : J - Non Super Boring Substring 
Source            : Codeforces Gym
Category          : String
Algorithm         : Hashing
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
typedef long long               ll;  
typedef unsigned long long      ull;  
  
// Generate random base in (before, after) open interval:  
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+1, after) (mt_rand);  
      return base % 2 == 0 ? base - 1 : base;  
}  
  
struct PolyHash  
{  
      //-------- Static variables ---------//  
      static const int mod = (int)1e9+123; // prime mod of polynomial hashing  
      static vector <int> pow1;            // powers of base modulo mod  
      static vector <ull> pow2;            // powers of base modulo 2^64  
      static int base;                     // base (point of hashing)  
      //-------- Static Functions --------//  
      static inline int diff(int a, int b)  
      {  
            // Difference between "a" and "b" modulo mod (0 <= a < mod, 0 <= b < mod)  
            return (a -= b) < 0 ? a + mod : a;  
      }  
      //-------- Variables of class ------//  
      vector <int> pref1; // Hash on prefix modulo mod  
      vector <ull> pref2; // Hash on prefix modulo 2^64  
      // Construct from string:  
      PolyHash(const string &s) : pref1(s.size() + 1u, 0), pref2(s.size() + 1u, 0)  
      {  
            assert(base < mod);  
            const int n = s.size(); // Firstly calculated needed power of base:  
            while((int)pow1.size() <= n)  
            {  
                  pow1.emplace_back(1LL * pow1.back() * base % mod);  
                  pow2.emplace_back(pow2.back() * base);  
            }  
            for (int i = 0; i < n; i++) // Fill arrays with polynomial hashes on prefix  
            {  
                  assert(base > s[i]);  
                  pref1[i+1] = (pref1[i] + 1LL * s[i] * pow1[i]) % mod;  
                  pref2[i+1] = pref2[i] + s[i] * pow2[i];  
            }  
      }  
      // Polynomial hash of subsequence [pos, pos+len)  
      // If mxPow != 0, value automatically multiply on base in needed power.  
      // Finally base ^ mxPow  
      inline pair<int, ull> operator () (const int pos, const int len, const int mxPow = 0) const  
      {  
            int hash1 = pref1[pos+len] - pref1[pos];  
            ull 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 PolyHash::base((int)1e9+7);  
vector <int> PolyHash::pow1{1};  
vector <ull> PolyHash::pow2{1};  
  
int main()  
{  
      // freopen("in.txt", "r", stdin);  
  
      PolyHash::base = gen_base(256, PolyHash::mod);  
      int tc;  
      cin >> tc;  
      for (int tcase = 1; tcase <= tc; tcase++)  
      {  
            int k;  
            string s, revs;  
            cin >> k >> s;  
            revs = s;  
            reverse(revs.begin(), revs.end());  
            int len = s.size();  
            const int mxPow = len;  
            // PolyHash::base = gen_base(256, PolyHash::mod);  
            PolyHash hash_s(s), hash_revs(revs);  
            ll ans = 0;  
            int i = 0, j = 0;  
            for ( ; j < len; j++)  
            {  
                  int nlen = j - i + 1;  
                  if (nlen < k)  
                  {  
                        ans += nlen;  
                        continue;  
                  }  
                  // check for k length palindrome  
                  int start_in_s = j - k + 1;  
                  int start_in_revs = len - j - 1;  
                  if (start_in_s >= 0 && hash_s(start_in_s, k, mxPow) == hash_revs(start_in_revs, k, mxPow))  
                  {  
                        i = start_in_s + 1;  
                        ans += j - i + 1;  
                        continue;  
                  }  
                  // check for k+1 length  
                  start_in_s -= 1;  
                  if (start_in_s >= 0 && hash_s(start_in_s, k+1, mxPow) == hash_revs(start_in_revs, k+1, mxPow))  
                  {  
                        i = start_in_s + 1;  
                        ans += j - i + 1;  
                        continue;  
                  }  
                  ans += j - i + 1;  
            }  
            cout << ans << "\n";  
      }  
}