[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;  
  
#define ll          long long int  
#define ull         unsigned long long int  
  
static const int maxn = 1e5 + 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+1, after) (mt_rand);  
      return base % 2 == 0 ? base - 1 : base;  
}  
  
int pow1[maxn];  
ull 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 <ll> pref1;  
      vector <ull> 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];  
            }  
      }  
      // Polynomial hash of subsequence [pos, pos+len)  
      // If mxPow != 0, value automatically multiply on base in needed power.  
      // Finally base ^ mxPow  
      // 0 - Indexed  
      pair <ll, ull> getHash(const int pos, const int len, const int mxPow = 0)  
      {  
            ll 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 main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout << fixed << setprecision(15);  
      #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++)  
      {  
            int k;  
            string s, revs;  
            cin >> k >> s;  
            revs = s;  
            reverse(revs.begin(), revs.end());  
            int len = s.size();  
            const int mxPow = len;  
            Hash hash_s = Hash(s);  
            Hash hash_revs = Hash(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.getHash(start_in_s, k, mxPow) == hash_revs.getHash(start_in_revs, k, mxPow))  
                  {  
                        i = start_in_s + 1;  
                        ans += j - i + 1;  
                        continue;  
                  }  
                  // check for k+1 length palindrome  
                  start_in_s -= 1;  
                  if (start_in_s >= 0 && hash_s.getHash(start_in_s, k+1, mxPow) == hash_revs.getHash(start_in_revs, k+1, mxPow))  
                  {  
                        i = start_in_s + 1;  
                        ans += j - i + 1;  
                        continue;  
                  }  
                  ans += j - i + 1;  
            }  
            cout << ans << '\n';  
      }  
}