滚动哈希

基本概念

滚动哈希是一种高效的字符串匹配算法，常用于解决模式匹配、最长公共子串等问题。它通过哈希函数快速计算字符串的哈希值，并利用前后子串的关系，在常数时间内更新哈希值。

基本原理

滚动哈希的核心思想是将字符串映射为整数，并使用这个整数进行比较。常见的哈希函数包括直接哈希法、幂次哈希法和旋转哈希法。滚动哈希利用字符串前后子串的关系，只需 O(1) 的时间即可计算新的哈希值。

具体来说，滚动哈希的计算公式如下：

hash(s)=(s[0]⋅basen−1+s[1]⋅basen−2+s[2]⋅basen−3+...+s[n−1])modmod

其中，hash(si…i+m−1) 表示从第 i 个字符开始长度为 m 的子串的哈希值，d 表示一个常数（通常取较大的质数，如 31、131 或 13331），si 和 si+m 表示字符串中第 i 个字符和第 i+m 个字符。

费曼理解

内部实现：

def rolling_hash(text, pattern):
   n = len(text)
   m = len(pattern)
   d = 31
   q = 10**9 + 7
   # 计算模式串的哈希值
   hp = 0
   for c in pattern:
       hp = (hp * d + ord(c)) % q
   # 计算文本串第一个窗口的哈希值
   ht = 0
   for c in text[:m]:
       ht = (ht * d + ord(c)) % q
   # 比较哈希值
   for i in range(n - m + 1):
       if ht == hp:
           if text[i:i + m] == pattern:
               return i
       if i < n - m:
           ht = ((ht - ord(text[i]) * pow(d, m-1, q)) * d + ord(text[i+m])) % q
   return -1