注意：减法后需处理负数（加 `prime` 再取模）。

哈希算法题目：Rabin-Karp 字符串匹配算法 题目描述： 给定一个文本字符串 text 和一个模式字符串 pattern ，请你实现 Rabin-Karp 算法，在 text 中查找所有 pattern 出现的位置。该算法通过哈希函数快速比较子串的哈希值，从而在平均情况下实现高效匹配。 解题过程循序渐进讲解 核心思想 Rabin-Karp 算法的核心是利用哈希函数计算模式串 pattern 的哈希值，以及文本串 text 中每个长度为 m （ m 为 pattern 的长度）的子串的哈希值。如果某个子串的哈希值与 pattern 的哈希值相等，则进一步验证该子串是否与 pattern 完全匹配（避免哈希冲突导致的误判）。 哈希函数设计 为了高效计算滑动窗口中的子串哈希值，我们采用"滚动哈希"（Rolling Hash）机制。常用的一种哈希函数是多项式哈希： 将字符串视为一个多进制数（例如基数为 base = 26 用于小写字母），计算其数值模一个大素数 prime 的结果。 公式：对于字符串 s ，哈希值 \[ \text{hash}(s) = (s[ 0] \times base^{m-1} + s[ 1] \times base^{m-2} + \dots + s[ m-1 ] \times base^0) \mod \text{prime} \] 选择大素数 prime 是为了减少哈希冲突，例如 10^9+7 。 滚动哈希计算步骤 预处理：计算 pattern 的哈希值 hash_pattern 。 初始化：计算 text 第一个长度为 m 的子串 text[0:m] 的哈希值 hash_window 。 滑动窗口：当窗口从 i 移动到 i+1 时，旧字符 text[i] 离开，新字符 text[i+m] 进入。新哈希值可通过以下公式快速计算： \[ \text{hash\_new} = (\text{hash\_old} - \text{text[ i]} \times base^{m-1}) \times base + \text{text[ i+m ]} \mod \text{prime} \] 注意：减法后需处理负数（加 prime 再取模）。 匹配验证 若 hash_window == hash_pattern ，则逐字符比较 text[i:i+m] 与 pattern ，确认是否完全匹配。 匹配成功则记录起始位置 i 。 复杂度分析 平均时间复杂度：O(n + m)，其中 n 为 text 长度。 最坏情况（大量哈希冲突）：O(n × m)，但通过合理选择 base 和 prime 可避免。 示例演示 设 text = "abracadabra" ， pattern = "abra" ， base = 26 ， prime = 10^9+7 。 计算 pattern 哈希值。 滑动窗口依次计算 "abra" 、 "brac" 、 "raca" … 的哈希值，与 pattern 比较。 在位置 0 和 7 找到匹配。 通过滚动哈希，Rabin-Karp 避免了每次重新计算子串哈希值，显著提升了效率。