哈希算法题目：Rabin-Karp 算法在二维矩阵中查找模式

字数 1868 2025-11-02 10:11:13

哈希算法题目：Rabin-Karp 算法在二维矩阵中查找模式

题目描述
给定一个二维字符矩阵 matrix（大小为 m x n）和一个二维模式矩阵 pattern（大小为 p x q），要求判断 pattern 是否在 matrix 中出现。你需要使用 Rabin-Karp 哈希算法高效解决此问题，避免暴力匹配的高时间复杂度。

解题过程

核心思路
Rabin-Karp 算法通过滚动哈希（Rolling Hash）在常数时间内计算子串哈希值，从而快速匹配模式。对于二维问题，需要将模式矩阵的哈希与矩阵中所有可能的 p x q 子矩阵的哈希进行比较。关键在于如何高效计算和更新二维子矩阵的哈希。
二维哈希计算
- 先对模式矩阵 pattern 计算一个基准哈希值。
- 对原矩阵 matrix，预先计算所有行的滚动哈希（一维），再对列方向进行滚动哈希（二维），从而快速得到每个 p x q 子矩阵的哈希。
- 哈希函数通常采用多项式哈希（Polynomial Hash），例如：

\[ H = \sum_{i=0}^{p-1} \sum_{j=0}^{q-1} (c_{ij} \cdot base_1^i \cdot base_2^j) \mod modulus \]

 其中 `base1` 和 `base2` 是基数，`modulus` 是大素数，避免溢出。

具体步骤
步骤1：预处理模式矩阵的哈希
- 计算 pattern 的哈希值 hash_pattern。
- 同时预处理 base1 的幂次（到 p 次方）和 base2 的幂次（到 q 次方），方便后续滚动计算。
步骤2：计算矩阵每行的滚动哈希（一维）
- 对矩阵每一行，用 Rabin-Karp 计算长度为 q 的连续子串哈希值，存入二维数组 row_hash[i][j]（表示第 i 行从 j 开始长度为 q 的子串哈希）。
- 例如，对第 i 行，从左到右滚动计算：

\[ row\_hash[i][j] = (row\_hash[i][j-1] - matrix[i][j-1] \cdot base_2^{q-1}) \cdot base_2 + matrix[i][j+q-1] \]

 需注意边界和取模。

步骤3：在列方向滚动计算二维子矩阵哈希

对每个起始列 j，计算一个高度为 p 的“列哈希”数组 col_hash，表示从第 j 列开始的 p x q 子矩阵的哈希。
首次计算第 0 行到 p-1 行的 row_hash[i][j] 的加权和（权重为 base1 的幂）：

\[ hash\_2d = \sum_{i=0}^{p-1} (row\_hash[i][j] \cdot base_1^i) \mod modulus \]

向下滚动时，移除最上一行的贡献，添加新一行的贡献：

\[ hash\_2d = ((hash\_2d - row\_hash[i-p][j] \cdot base_1^{p-1}) \cdot base_1 + row\_hash[i][j]) \mod modulus \]

步骤4：哈希比较与验证

遍历所有可能的子矩阵位置（i 从 0 到 m-p，j 从 0 到 n-q），若 hash_2d == hash_pattern，则需进一步验证（因哈希可能冲突），逐字符比较 pattern 和当前子矩阵。
若匹配成功则返回 true；否则继续扫描。

复杂度分析
- 预处理：O(mn + pq)
- 滚动计算：O(mn)
- 最坏情况下验证耗时 O(mnpq)，但实际因哈希过滤很少发生。
- 整体优于暴力 O(mnpq)。

示例（简化数值方便理解）：
设 matrix = [['a','b'],['c','d']]，pattern = [['b'],['d']]，base1=2, base2=3, modulus=1e9+7。

模式哈希：hash_pattern = ('b'*3^0 + 'd'*3^1 * 2^1) mod modulus（实际用ASCII码值）。
矩阵行哈希：计算每行长度为1的哈希，再在列方向滚动得到 p x q=2x1 子矩阵哈希，与模式比较。

通过以上步骤，可高效解决二维模式匹配问题。

哈希算法题目：Rabin-Karp 算法在二维矩阵中查找模式题目描述给定一个二维字符矩阵 matrix （大小为 m x n ）和一个二维模式矩阵 pattern （大小为 p x q ），要求判断 pattern 是否在 matrix 中出现。你需要使用 Rabin-Karp 哈希算法高效解决此问题，避免暴力匹配的高时间复杂度。解题过程核心思路 Rabin-Karp 算法通过滚动哈希（Rolling Hash）在常数时间内计算子串哈希值，从而快速匹配模式。对于二维问题，需要将模式矩阵的哈希与矩阵中所有可能的 p x q 子矩阵的哈希进行比较。关键在于如何高效计算和更新二维子矩阵的哈希。二维哈希计算先对模式矩阵 pattern 计算一个基准哈希值。对原矩阵 matrix ，预先计算所有行的滚动哈希（一维），再对列方向进行滚动哈希（二维），从而快速得到每个 p x q 子矩阵的哈希。哈希函数通常采用多项式哈希（Polynomial Hash），例如： \[ H = \sum_ {i=0}^{p-1} \sum_ {j=0}^{q-1} (c_ {ij} \cdot base_ 1^i \cdot base_ 2^j) \mod modulus \] 其中 base1 和 base2 是基数， modulus 是大素数，避免溢出。具体步骤步骤1：预处理模式矩阵的哈希计算 pattern 的哈希值 hash_pattern 。同时预处理 base1 的幂次（到 p 次方）和 base2 的幂次（到 q 次方），方便后续滚动计算。步骤2：计算矩阵每行的滚动哈希（一维）对矩阵每一行，用 Rabin-Karp 计算长度为 q 的连续子串哈希值，存入二维数组 row_hash[i][j] （表示第 i 行从 j 开始长度为 q 的子串哈希）。例如，对第 i 行，从左到右滚动计算： \[ row\_hash[ i][ j] = (row\_hash[ i][ j-1] - matrix[ i][ j-1] \cdot base_ 2^{q-1}) \cdot base_ 2 + matrix[ i][ j+q-1 ] \] 需注意边界和取模。步骤3：在列方向滚动计算二维子矩阵哈希对每个起始列 j ，计算一个高度为 p 的“列哈希”数组 col_hash ，表示从第 j 列开始的 p x q 子矩阵的哈希。首次计算第 0 行到 p-1 行的 row_hash[i][j] 的加权和（权重为 base1 的幂）： \[ hash\_2d = \sum_ {i=0}^{p-1} (row\_hash[ i][ j] \cdot base_ 1^i) \mod modulus \] 向下滚动时，移除最上一行的贡献，添加新一行的贡献： \[ hash\_2d = ((hash\_2d - row\_hash[ i-p][ j] \cdot base_ 1^{p-1}) \cdot base_ 1 + row\_hash[ i][ j ]) \mod modulus \] 步骤4：哈希比较与验证遍历所有可能的子矩阵位置（ i 从 0 到 m-p ， j 从 0 到 n-q ），若 hash_2d == hash_pattern ，则需进一步验证（因哈希可能冲突），逐字符比较 pattern 和当前子矩阵。若匹配成功则返回 true ；否则继续扫描。复杂度分析预处理：O(mn + pq) 滚动计算：O(mn) 最坏情况下验证耗时 O(mnpq)，但实际因哈希过滤很少发生。整体优于暴力 O(mnpq)。示例（简化数值方便理解）：设 matrix = [['a','b'],['c','d']] ， pattern = [['b'],['d']] ， base1=2, base2=3, modulus=1e9+7 。模式哈希： hash_pattern = ('b'*3^0 + 'd'*3^1 * 2^1) mod modulus （实际用ASCII码值）。矩阵行哈希：计算每行长度为1的哈希，再在列方向滚动得到 p x q=2x1 子矩阵哈希，与模式比较。通过以上步骤，可高效解决二维模式匹配问题。