哈希算法题目：Rabin-Karp 算法在二维矩阵中查找模式
题目描述
给定一个大小为 \(m \times n\) 的二维矩阵（文本矩阵）和一个大小为 \(p \times q\) 的二维模式矩阵，要求使用 Rabin-Karp 算法高效地查找模式矩阵在文本矩阵中出现的所有位置。文本矩阵和模式矩阵中的元素可以是字符或整数。
解题过程循序渐进讲解
步骤1：理解核心思想——滚动哈希的扩展
- Rabin-Karp 算法的核心是通过哈希值快速比较数据段。在一维字符串中，我们通过滑动窗口计算滚动哈希；在二维问题中，需要将滚动哈希扩展到二维窗口。
- 基本思路：
- 计算模式矩阵的哈希值 \(H_{\text{pattern}}\)。
- 计算文本矩阵中每个可能的 \(p \times q\) 子矩阵的哈希值。
- 若子矩阵的哈希值与 \(H_{\text{pattern}}\) 匹配，再逐元素验证（避免哈希冲突）。
- 利用滚动哈希优化：在文本矩阵中滑动窗口时，仅需增量更新哈希值，而非重新计算整个子矩阵的哈希。
步骤2：设计二维哈希函数
- 假设矩阵元素为整数（字符可转换为 ASCII 值）。
- 选择两个基数 \(B_1\) 和 \(B_2\)（通常为质数），分别用于行方向和列方向的哈希计算。
- 对于一个 \(p \times q\) 的子矩阵，其哈希值计算公式为：
\[ H = \sum_{i=0}^{p-1} \sum_{j=0}^{q-1} \text{matrix}[i][j] \cdot B_1^{p-1-i} \cdot B_2^{q-1-j} \]
此公式将二维矩阵视为一个 \(p \times q\) 的“数字”，其中每行类似一个高基数的数字位。
步骤3：预处理文本矩阵的哈希值
- 为了支持滚动更新，需预先计算文本矩阵的“前缀哈希数组”。
- 定义二维前缀哈希数组 \(\text{prefix}[i][j]\) 表示从 \((0,0)\) 到 \((i-1, j-1)\) 子矩阵的哈希值（需调整索引边界）。
- 实际实现中，可直接计算每个可能的 \(p \times q\) 窗口的哈希值，但通过以下步骤优化：
步骤4：列方向的滚动哈希（固定行方向）
- 第一步：对文本矩阵的每一行，计算长度为 \(q\) 的滚动哈希序列
- 使用一维 Rabin-Karp 方法，以基数 \(B_2\) 计算每行中所有长度为 \(q\) 的窗口的哈希值，结果存于二维数组 \(\text{rowHash}[i][j]\)（表示第 \(i\) 行从列 \(j\) 开始的长度为 \(q\) 的窗口哈希值）。
- 例如，对第 \(i\) 行：
\[ \text{rowHash}[i][j] = \sum_{k=0}^{q-1} \text{matrix}[i][j+k] \cdot B_2^{q-1-k} \]
滑动时通过减去最高位、乘以 $ B_2 $、加上新元素来更新哈希。
- 第二步：在列方向滚动计算 \(p \times q\) 子矩阵哈希
- 将 \(\text{rowHash}[i][j]\) 视为一维数组中的元素，再以基数 \(B_1\) 在列方向计算长度为 \(p\) 的窗口的哈希值。
- 对于固定的列起始位置 \(j\)，计算从行 \(i\) 开始的 \(p\) 行对应的 \(\text{rowHash}[i][j]\) 的哈希值：
\[ H_{\text{sub}} = \sum_{k=0}^{p-1} \text{rowHash}[i+k][j] \cdot B_1^{p-1-k} \]
- 滑动窗口向下移动一行时：
\[ H_{\text{new}} = (H_{\text{old}} - \text{rowHash}[i][j] \cdot B_1^{p-1}) \cdot B_1 + \text{rowHash}[i+p][j] \]
步骤5：算法流程
- 计算模式矩阵的哈希值 \(H_{\text{pattern}}\)（使用相同的 \(B_1, B_2\)）。
- 对文本矩阵的每一行，计算所有长度为 \(q\) 的窗口的滚动哈希值 \(\text{rowHash}[i][j]\)。
- 对于每个列起始位置 \(j\)（\(0 \leq j \leq n-q\)）：
- 初始化一个列方向的滚动哈希，计算前 \(p\) 行的 \(\text{rowHash}[i][j]\) 的哈希值。
- 从第 \(p-1\) 行开始向下滑动窗口，每次比较当前哈希与 \(H_{\text{pattern}}\)。若匹配，则逐元素验证子矩阵。
- 更新滚动哈希并移动到下一行。
步骤6：处理哈希冲突与边界条件
- 由于哈希值可能冲突，当哈希匹配时必须逐元素验证子矩阵。
- 注意模运算：实际计算中需对一个大质数（如 \(10^9+7\)）取模，避免溢出。
- 时间复杂度：预处理 \(O(mn)\)，滑动窗口比较 \(O((m-p+1)(n-q+1))\)，最坏情况下（哈希冲突多）为 \(O(mnpq)\)，但平均效率高。
总结
通过将一维滚动哈希扩展到行列两个方向，Rabin-Karp 算法能高效解决二维模式匹配问题。关键点在于分离行列方向的哈希计算，并利用滚动更新避免重复计算。