Rabin-Karp算法（字符串匹配）

描述
Rabin-Karp算法是一种基于哈希的字符串匹配算法，用于在一个主文本串中查找一个模式串的出现位置。其核心思想是通过计算模式串和文本串中滑动窗口的哈希值，快速比较是否可能匹配。若哈希值匹配，再进一步验证实际字符是否相等，从而减少不必要的字符比对。

解题过程

1. 哈希函数设计
   • 选择一种滚动哈希函数，使得当前窗口的哈希值可以通过前一个窗口的哈希值快速计算。常用多项式哈希：

\[ H(s) = (s[0] \cdot d^{m-1} + s[1] \cdot d^{m-2} + \dots + s[m-1] \cdot d^0) \mod q \]

 其中 $d$ 是字符集大小（如256），$m$ 是模式串长度，$q$ 是一个大素数以减少哈希冲突。

2. 预处理阶段

   • 计算模式串的哈希值 \(H_{\text{pattern}}\)。
   • 计算文本串前 \(m\) 个字符的初始哈希值 \(H_{\text{window}}\)。

3. 滑动窗口匹配

   • 从文本串起始位置开始，依次滑动窗口（每次右移一位）：
     • 若 \(H_{\text{window}} = H_{\text{pattern}}\)，则逐字符比较窗口内容与模式串。
     • 更新下一个窗口的哈希值：

\[ H_{\text{new}} = (d \cdot (H_{\text{old}} - s[i] \cdot d^{m-1}) + s[i+m]) \mod q \]

   其中 $s[i]$ 是离开窗口的字符，$s[i+m]$ 是新进入的字符。  

• 为避免负数，可在计算中添加 \(q\) 再取模。

4. 时间复杂度分析
   • 平均情况：\(O(n+m)\)，最坏情况（哈希冲突频繁）退化为 \(O(nm)\)。
   • 通过合理选择 \(q\) 可降低冲突概率。

示例
假设文本串 "ABABDABAC"，模式串 "ABA"，\(d=256, q=101\)：

1. 计算模式串哈希： \(H_{\text{pattern}} = (65\cdot256^2 + 66\cdot256^1 + 65\cdot256^0) \mod 101 = 30\)。
2. 初始窗口 "ABA" 哈希同样为 30，逐字符验证匹配。
3. 滑动窗口后更新哈希，继续匹配。

通过滚动哈希避免重复计算，Rabin-Karp在多个模式匹配或大数据流中尤为高效。