Rabin-Karp 算法在二维矩阵中查找模式

题目描述：给定一个较大的二维字符矩阵（文本矩阵）和一个较小的二维字符矩阵（模式矩阵），要求使用Rabin-Karp算法的高效哈希技术，在文本矩阵中查找所有模式矩阵出现的位置。

解题过程：

1. 问题分析

   • 我们需要在较大的m×n文本矩阵T中查找较小的p×q模式矩阵P的所有出现位置
   • 暴力解法需要O(mnpq)的时间复杂度，对于大矩阵效率很低
   • Rabin-Karp算法通过滚动哈希技术可以将时间复杂度优化到O(mn)

2. 核心思想：二维滚动哈希

   • 将二维哈希分解为两个一维哈希过程
   • 首先计算每一行的滚动哈希，然后基于行哈希结果计算列的滚动哈希
   • 使用合适的哈希函数和模运算来避免数值溢出

3. 哈希函数设计

   • 选择基数base1和base2（通常选择质数）
   • 选择大质数MOD作为模数（如10^9+7）
   • 哈希值计算：hash = Σ(T[i][j] × base1^i × base2^j) mod MOD

4. 具体实现步骤

   步骤1：预计算幂次表

   # 预计算base1和base2的各次幂
   pow1[i] = base1^i mod MOD
   pow2[j] = base2^j mod MOD
   

   步骤2：计算文本矩阵的哈希值

   • 先计算每一行的哈希值（水平方向滚动哈希）
   • 再基于行哈希结果计算二维窗口的哈希值（垂直方向滚动哈希）

   步骤3：模式矩阵哈希计算

   pattern_hash = 0
   for i in range(p):      # 行
       for j in range(q):  # 列  
           pattern_hash = (pattern_hash + ord(P[i][j]) * pow1[i] * pow2[j]) % MOD
   

   步骤4：滚动哈希匹配

   • 在文本矩阵中滑动p×q的窗口
   • 使用滚动哈希技术快速计算每个窗口的哈希值
   • 当窗口哈希值与模式哈希值匹配时，进行精确验证（防止哈希冲突）

5. 滚动哈希的优化技巧

   • 水平滚动：当窗口右移时，减去最左列，加上最右列
   • 垂直滚动：当窗口下移时，减去最上行，加上最下行
   • 每次滚动操作都是O(1)时间复杂度的计算

6. 哈希冲突处理

   • 由于使用模运算，可能存在不同矩阵有相同哈希值的情况
   • 当哈希值匹配时，必须进行逐字符的精确比较来确认真正匹配
   • 选择足够大的MOD可以降低冲突概率

这种二维Rabin-Karp算法将时间复杂度从O(mnpq)优化到O(mn)，是处理大矩阵模式匹配的高效解决方案。