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

题目描述：给定一个m x n的二维字符矩阵text和一个a x b的二维字符矩阵pattern（其中a ≤ m, b ≤ n），要求在text中查找是否存在与pattern完全相同的子矩阵。如果存在，返回所有匹配位置的左上角坐标。

解题过程：

1. 问题分析：

   • 这是一个二维的模式匹配问题，暴力解法需要O(mna*b)的时间复杂度
   • 我们可以将Rabin-Karp算法从一维扩展到二维，利用滚动哈希来优化匹配效率
   • 核心思想：先计算pattern的哈希值，然后在text中滑动计算相同大小的子矩阵哈希值

2. 哈希函数设计：

   • 选择两个质数p和q作为基数（通常选择较大的质数，如10^9+7等）
   • 对于矩阵中的每个元素，我们可以将其字符编码为数字（如ASCII码）
   • 二维哈希公式：H = Σ(i=0 to a-1) Σ(j=0 to b-1) matrix[i][j] * p^i * q^j mod M

3. 预处理阶段：

   • 计算pattern矩阵的哈希值H_pattern
   • 预计算p和q的各次幂模M的值，用于后续的滚动计算
   • 计算text中每一行的滚动哈希（一维Rabin-Karp）

4. 具体步骤：
   a. 对text的每一行，使用一维Rabin-Karp计算所有长度为b的窗口哈希值
   b. 在垂直方向上，对步骤a得到的结果再次使用Rabin-Karp算法
   c. 具体来说：

   • 先计算每行中所有长度为b的窗口哈希，得到新的二维数组hash_rows
   • 然后在hash_rows的列方向上，计算长度为a的窗口哈希
   • 这个最终得到的哈希值就是a x b子矩阵的哈希值

5. 哈希碰撞处理：

   • 当发现哈希值匹配时，需要进行逐字符验证以确保不是假阳性
   • 这是由于哈希函数可能产生碰撞，虽然概率很低但仍需验证

6. 时间复杂度分析：

   • 预处理：O(mn + ab)
   • 主要计算：O(m*n)
   • 总体优于暴力解法的O(mna*b)

7. 优化技巧：

   • 使用双哈希（两个不同的模数）可以进一步降低碰撞概率
   • 合理选择基数p和q，最好选择大于字符集大小的质数

这个算法将二维匹配问题转化为两次一维匹配，充分利用了Rabin-Karp算法的滚动哈希特性，在保持正确性的同时显著提高了效率。