基于滚动哈希的字符串匹配：Rabin-Karp算法详解

题目描述
设计一个字符串匹配算法，在文本串text中查找模式串pattern的所有出现位置。要求利用滚动哈希（Rabin-Karp算法）实现高效匹配，避免在每次滑动窗口时重新计算整个子串的哈希值。算法需处理哈希冲突，确保结果正确。

解题过程

1. 核心思想
Rabin-Karp算法通过哈希函数将字符串映射为整数，比较哈希值而非字符串本身。若哈希值匹配，再逐字符验证以避免哈希冲突。关键优化是使用滚动哈希：当窗口滑动时，新的哈希值基于旧哈希值增量计算，时间复杂度从O(mn)降至O(n+m)。

2. 哈希函数设计

• 将字符串视为某进制（如基数base）的数。例如，字符串"abc"在基数为26时可表示为：
  hash = a * 26² + b * 26¹ + c * 26⁰。
• 为避免溢出，对一个大素数mod取模。

3. 滚动哈希计算步骤
假设文本串长度为n，模式串长度为m：

• 步骤1：预处理模式串哈希
  计算模式串pattern的哈希值hash_pattern。
  同时计算base^(m-1) % mod（记为high_base），用于后续滚动时移除最高位字符。

• 步骤2：初始化文本窗口哈希
  计算文本串前m个字符的哈希值hash_window。

• 步骤3：滑动窗口并更新哈希
  遍历文本串从索引m到n-1的每个位置：

  1. 若hash_window == hash_pattern，逐字符比较窗口子串与模式串。
  2. 更新滚动哈希：移除窗口最左字符，加入新字符：

     hash_window = (hash_window - left_char * high_base) * base + new_char
     hash_window %= mod  # 确保非负
     

4. 冲突处理
哈希值相等时可能发生冲突（不同字符串哈希相同）。因此需在哈希匹配后执行二次验证，逐字符比较窗口子串与模式串。

5. 示例演示
文本串text = "abracadabra"，模式串pattern = "abra"，设base=26, mod=1000007：

• hash_pattern = (0*26³ + 1*26² + 17*26¹ + 0*26⁰) % mod = 11478（a=0, b=1, r=17）。
• 初始窗口"abra"哈希同hash_pattern，匹配成功。
• 滑动到"brac"：
  旧哈希减'a'*26³，乘26，加'c'，得新哈希。继续比较。

6. 复杂度分析

• 时间复杂度：平均O(n+m)，最坏O(nm)（当哈希冲突频繁时）。
• 空间复杂度：O(1)（除存储结果外无额外空间）。

7. 优化技巧

• 选择大素数mod减少冲突。
• 双哈希策略：用两个不同基数和模数计算哈希，仅当双哈希均匹配时才验证，进一步降低冲突概率。

通过滚动哈希避免重复计算，Rabin-Karp算法在长文本匹配中显著提升效率，尤其适用于多模式匹配（结合哈希表存储模式集）。