https://leetcode.com/problems/find-substring-with-given-hash-value/
顺便看看Rabin-Karp算法，以及和这个题的关系，以及取模操作的一些性质
题目本身还是很经典的！

个人解答

  1. class Solution:
  2.     def subStrHash(self, s: str, p: int, m: int, k: int, h: int) -> str:
  3.         def val(x):
  4.             return ord(x) - ord('a') + 1
  6.         min_i = len(s)
  7.         max_factor = pow(p, k - 1, m)
  9.         v = 0
  10.         for i in range(len(s) - 1, len(s) - k - 1, -1):
  11.             v = (v * p + val(s[i])) % m
  12.         if v == h:
  13.             min_i = len(s) - k
  15.         for i in range(len(s) - k - 1, -1, -1):
  16.             v = ((v - max_factor * val(s[i + k])) * p + val(s[i])) % m
  17.             if v == h:
  18.                 min_i = i
  20.         return s[min_i:min_i + k]

题目分析

Rabin-Karp算法

其实题目描述就是类似Rabin-Karp算法：https://www.geeksforgeeks.org/rabin-karp-algorithm-for-pattern-searching/
这个算法的大致描述如下：
在进行字符串匹配的时候，可以先比较字串和pattern的hash值，如果相同，再进一步比较。思路显而易见，但是如何高效计算hash很重要。
这个算法采用了如下的递推公式：

  1. hash( txt[s+1 .. s+m] ) = ( d ( hash( txt[s .. s+m-1]) – txt[s]*h ) + txt[s + m] ) mod q 
  2. hash( txt[s .. s+m-1] ) : Hash value at shift s. 
  3. hash( txt[s+1 .. s+m] ) : Hash value at next shift (or shift s+1) 
  4. d: Number of characters in the alphabet 
  5. q: A prime number 
  6. h: d^(m-1)

理解起来，就是减去高位的数，整体移一位之后再加上新的低位就好：

This is simple mathematics, we compute decimal value of current window from previous window. For example pattern length is 3 and string is “23456” You compute the value of first window (which is “234”) as 234. How how will you compute value of next window “345”? You will do (234 – 2100)10 + 5 and get 345.

所以，这个算法里，左侧是高位，右侧是低位，这样从左往右就能够进行上述的递推。

本题分析

本题里的递推公式高位低位是相反的：

  1. hash(s, p, m) = (val(s[0]) * p0 + val(s[1]) * p1 + ... + val(s[k-1]) * pk-1) mod m

直接从左往右算的话，涉及到了除法，而在取模的情况下，除法是比较难处理的，因此需要适当变换一下，从右往左操作。如题解里边所示，基本和Rabin-Karp算法的流程相同，无非是从右往左计算。

取模性质

算法题中涉及很多取模运算，有时候一些性质还是要知道的。
https://zh.wikipedia.org/wiki/%E6%A8%A1%E9%99%A4

  • 恒等式：
    • (a mod n) mod n = a mod n
    • 对所有的正数 x 有：n^x mod n = 0
    • 如果 p 是一个质数，且不为 b 的因数，此时由费马小定理有：a * b^(p−1) mod p = a mod p
  • 逆运算：
    • [(−a mod n) + (a mod n)] mod n = 0.
    • b^−1 mod n 表示模反元素。当且仅当 b 与 n 互质时，等式左侧有定义：[(b^−1 mod n)(b mod n)] mod n = 1。
  • 分配律：
    • (a + b) mod n = [(a mod n) + (b mod n)] mod n
    • ab mod n = [(a mod n)(b mod n)] mod n
    • d mod (abc) = (d mod a) + a[(d \ a) mod b] + ab[(d \ a \ b) mod c]，符号 \ 是欧几里德除法中的除法操作符，运算结果为商
    • c mod (a+b) = (c mod a) + [bc \ (a+b)] mod b - [bc \ (a + b)] mod a.
  • 除法定义：仅当式子右侧有定义时，即 b、n 互质时有：ab mod n = [(a mod n)(b−1 mod n)] mod n，其他情况为未定义的。
  • 乘法逆元：[(ab mod n)(b−1 mod n)] mod n = a mod n.