字符串匹配的Rabin-Karp算法

1. 问题描述
Rabin-Karp算法是一种基于哈希的字符串匹配算法，用于在文本串中查找模式串的出现位置。其核心思想是：通过计算模式串和文本串中各个子串的哈希值，快速比较是否匹配。若哈希值相等，则进一步验证实际字符是否相同（避免哈希冲突）。该算法平均时间复杂度为O(n+m)，其中n为文本串长度，m为模式串长度。

2. 核心思想：滚动哈希
传统方法逐字符比较文本串中每个长度为m的子串，复杂度为O(n*m)。Rabin-Karp通过滚动哈希优化：

• 计算模式串的哈希值hash_p。
• 计算文本串前m个字符的哈希值hash_t。
• 滑动窗口时，利用前一个子串的哈希值快速计算新子串的哈希值，避免重新计算整个子串。

3. 哈希函数设计
假设字符集大小为d（如ASCII码d=256），将字符串视为d进制数，再取模大素数q（减少哈希冲突）。例如字符串"abc"的哈希值计算：

hash = (a * d² + b * d¹ + c * d⁰) mod q

其中a、b、c为字符对应的整数值（如ASCII码）。

4. 滚动计算步骤
设文本串为T，模式串为P，长度分别为n和m，d为字符集大小，q为素数。

• 步骤1：预处理
  计算模式串P的哈希值hash_p，以及文本串第一个子串T[0..m-1]的哈希值hash_t。
  同时计算h = d^(m-1) mod q（用于后续滚动时移除最高位字符）。

• 步骤2：滑动窗口比较
  从i=0到i=n-m遍历文本串：

  1. 若hash_t == hash_p，则逐字符比较T[i..i+m-1]与P，确认是否匹配。
  2. 计算下一个子串的哈希值（i从0到n-m-1时）：

     hash_t = (d * (hash_t - T[i] * h) + T[i+m]) mod q
     

     解释：
     • T[i] * h对应移除窗口首字符的贡献。
     • 乘以d相当于左移一位，加上新字符T[i+m]完成更新。
     • 取模保证结果在[0, q-1]范围内。

5. 处理负数取模
计算hash_t - T[i] * h可能为负数，需调整为正数后再取模：

hash_t = (d * (hash_t - T[i] * h) + T[i+m]) % q
if hash_t < 0:
    hash_t += q

6. 算法示例
文本串T="3141592653"，模式串P="4159"，d=10（数字字符集），q=13。

• 计算h=10³ mod 13=12。
• hash_p = 4159 mod 13=8。
• 初始子串T[0..3]="3141"：hash_t=3141 mod 13=6。
• 滑动窗口：
  • i=0: hash_t=6≠8，更新哈希值：
    hash_t = (10*(6-3*12)+5) mod 13 = (10*(-30)+5) mod 13 = -295 mod 13=8（调整后）。
  • i=1: hash_t=8等于hash_p，逐字符验证T[1..4]="4159"匹配成功。

7. 复杂度分析

• 预处理：计算h和初始哈希值O(m)。
• 滑动窗口：O(n)次哈希计算，每次O(1)。
• 最坏情况：每次哈希匹配都需逐字符验证（如模式串"aaa"在文本串"aaaaaaaa"中），复杂度O(n*m)。但实际中通过合理选择q可降低冲突概率。

8. 应用场景

• 多模式匹配（结合哈希表存储多个模式串的哈希值）。
• plagiarism检测、DNA序列比对等需要快速过滤不匹配的场景。