https://leetcode.com/contest/weekly-contest-278/problems/find-substring-with-given-hash-value/
1st try: time limit exceed
2nd try: time limit exceed (pre computing)
3rd try: pass (pre computing more)
class Solution:
def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:
xa = [1+ord(ch)-ord('a') for ch in s]
xb = [1] * (k+1)
for i in range(1, k+1):
xb[i] = (xb[i-1] * power) % modulo
n = len(xa)
h = sum(xa[n-k+i]*xb[i] for i in range(k))
r = n-k
for i in range(n-k-1, -1, -1):
h = (h*power + xa[i] - xa[i+k]*xb[k]) % modulo
if h == hashValue:
r = i
return s[r:r+k]