Find Substring With Given Hash Value LeetCode solution in C++

1
''' class Solution { public : string subStrHash(string s, int power, int modulo,
2
                                                int k, int hashValue) {
3
  int n = s.size();
4
  long long int sum = 0;
5
  long long int p = 1;
6
  // Intializing a window from end of size k
7
  for (int i = 0; i < k; i++) {
8
    sum = (sum + ((s[n - k + i] - 'a' + 1) * p));
9
    if (i != k - 1) p = (p * power) % modulo;
10
  }
11
  // storing the res when ever we get required answer
12
  int res = n - k; // storing the res when ever we get required answer
13
                   // slide window to right and removing ith index element and
14
                   // adding (i-k)th index element
15
  for (int i = n - 1; i >= k; i--) {
16
    // removing last element from window
17
    sum -= (s[i] - 'a' + 1) * (p % modulo);
18
    // dividing by modulo to avoid integer overflow conditions
19
    sum = sum % modulo;
20
    // muliplying the given string by power
21
    sum = sum * (power % modulo);
22
    // adding (i-k)th element in the window
23
    sum += s[i - k] - 'a' + 1;
24
    // if sum < 0 then it created problem in modulus thats why making it
25
    // positive
26
    while (sum % modulo < 0) {
27
      sum = sum + modulo;
28
    }
29
    if (sum % modulo == hashValue) {
30
      res = i - k; // storing the starting window index because we have to
31
                   // return the first string from starting
32
    }
33
  }
34
  return s.substr(res, k);
35
}
36
}
37
;
38
'''