First time using rolling hash to AC a problem

Minimum Time to Revert Word to Initial State II — LeetCode Contest

This is a LC contest problem. If you participate in this contest, you may know that interesting python O(n²) solution can get AC. Then after the contest, the LC team update the test case, meanwhile, change the constraints of the question from

1 <= word.length <= 10^5

to

1 <= word.length <= 10^6

Then my submission failed, not because of the time complexity too high, but because the static size vector out of boundary.

Specifically the 3rd line:

const int MAX_N = 100010;

should be changed to following to make it work

const int MAX_N = 1000010;

Although, it is not professional to change the constraints, seems we don’t need complain as they provide free contest?

Minimum Time to Revert Word to Initial State II — LeetCode Contest

Here is a solution of using rolling hash to solve this problem.

typedef long long ll;
typedef vector<int> vi;
const int MAX_N = 1000010;
const int p = 131;                               // p and M are
const int M = 1e9+7;                             // relatively prime

int Pow[MAX_N];   

vi computeRollingHash(string &T) {                      // Overall: O(n)
    //vi Pow(MAX_N,0);  
    vi h(MAX_N, 0);   
    const int n = T.size();
  Pow[0] = 1;                                    // compute p^i % M
  for (int i = 1; i < n; ++i)                    // O(n)
    Pow[i] = ((ll)Pow[i-1]*p) % M;
  h[0] = 0;
  for (int i = 0; i < n; ++i) {                  // O(n)
    if (i != 0) h[i] = h[i-1];                   // rolling hash
    h[i] = (h[i] + ((ll)T[i]*Pow[i]) % M) % M;
  }
    return h;
}

int extEuclid(int a, int b, int &x, int &y) {    // pass x and y by ref
  int xx = y = 0;
  int yy = x = 1;
  while (b) {                                    // repeats until b == 0
    int q = a/b;
    tie(a, b) = tuple(b, a%b);
    tie(x, xx) = tuple(xx, x-q*xx);
    tie(y, yy) = tuple(yy, y-q*yy);
  }
  return a;                                      // returns gcd(a, b)
}

int modInverse(int b, int m) {                   // returns b^(-1) (mod m)
  int x, y;
  int d = extEuclid(b, m, x, y);                 // to get b*x + m*y == d
  if (d != 1) return -1;                         // to indicate failure
  // b*x + m*y == 1, now apply (mod m) to get b*x == 1 (mod m)
  return (x+m)%m;                                // this is the answer
}


int hash_fast(int L, int R, vi &h) {                    // O(1) hash of any substr
  if (L == 0) return h[R];                       // h is the prefix hashes
  int ans = 0;
  ans = ((h[R] - h[L-1]) % M + M) % M;           // compute differences
  ans = ((ll)ans * modInverse(Pow[L], M)) % M;   // remove P[L]^-1 (mod M)
  return ans;
}


class Solution {
public:
    int minimumTimeToInitialState(string word, int k) {
        vi h = computeRollingHash(word);
        const int n = word.size();
        if (n == k)return 1;
        const int M = (n + k - 1) / k;
        int left = 0;
        int sz = 0;
        for (int i = 1; i <= M; ++i){
            left = i*k;
            if (left >= n)return i;
            sz = n - left;
           // cout << i<<" "<<left << endl;
            //cout << word.substr(left)<<endl;
            int h1 = hash_fast(0, sz -1, h);
            int h2 = hash_fast(left, n-1, h);
            if (h1 == h2)return i;
            
            
        }
        return -1;
        
    }
};