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 areconst int M = 1e9+7;                             // relatively primeint 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;            }};`

--

--