滑动窗口，我的思路没问题
但是超时了，不是时间复杂度，而是大数运算超时。。。

class Solution:def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:# 不用每次都算一次，根据前一个的关系算def val(c):return ord(c) - ord('a') + 1left = 0right = k - 1sum = 0for i in range(k): sum += val(s[i]) * pow(power, i)while sum % modulo != hashValue:sum -= val(s[left])sum //= powerleft += 1right += 1sum += val(s[right]) * pow(power, k - 1)#print(left)#print(sum)return s[left: right + 1]

有一个很重要的问题，除法不满足mod的恒等性！！！
除法取模要考虑逆元，后面碰到再说，我记得rsa似乎做过这个东东
把能加mod的地方都加mod
因为顺序除，所以倒序就是乘，所以我们考虑倒序

正确答案：

class Solution:def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:# 不用每次都算一次，根据前一个的关系算def val(c):return ord(c) - ord('a') + 1n = len(s)left = n - kright = n - 1    sum = 0myLeft = -1myRight = -1# 倒序求，使得滑动窗口的关系为乘（保持mod恒等）for i in range(k): sum += val(s[n - 1 - i]) * pow(power, k - 1 - i, modulo)sum %= modulowhile left >= 0:# 更新到反序最后的，也就是正序最早的if sum % modulo == hashValue:myLeft = leftmyRight = right# 去掉最右边的k-1次幂sum = (sum - (val(s[right]) * pow(power, k - 1, modulo))) % modulo# 同乘psum = (sum * power) % modulo# 滑动left -= 1right -= 1# 补上左边if left >= 0:sum = (sum + val(s[left])) % modulo           #print(left)#print(sum)return s[myLeft: myRight + 1]

总结：
细节太多，确实考试的时候做不出来，不够熟练

划重点：
求商的时候mod不恒等，要转换成乘法
注意要取正向第一个，也就是反向最后一个