Rabin-Karp 算法在二进制矩阵中查找重复模式
字数 2703 2025-12-10 15:29:59

Rabin-Karp 算法在二进制矩阵中查找重复模式

题目描述
给定一个由 0 和 1 组成的二进制矩阵（二维数组），矩阵大小为 m x n。请设计一个算法，查找在矩阵中至少重复出现两次的、尺寸为 a x b 的子矩阵（模式），并返回第一个匹配的左上角坐标。如果不存在重复子矩阵，则返回 (-1, -1)。要求算法时间复杂度尽可能高效，尤其当矩阵较大时，应避免暴力匹配。

解题过程循序渐进讲解

步骤1：理解问题与暴力解法瓶颈
我们需要在 m x n 的二进制矩阵中，找到任意一个至少出现两次的 a x b 子矩阵（a ≤ m, b ≤ n）。最直接的方法是：

  1. 枚举所有 a x b 子矩阵的左上角位置 (i, j)，其中 0 ≤ i ≤ m-a, 0 ≤ j ≤ n-b。
  2. 对每个子矩阵提取其二进制模式，存储到一个哈希表中。
  3. 当发现某个模式已存在时，即找到重复，返回第一个匹配的左上角坐标。

暴力法的瓶颈：提取每个 a x b 子矩阵需要 O(ab) 时间，总共有 (m-a+1)(n-b+1) 个子矩阵，总复杂度为 O(mna*b)，当矩阵较大时非常慢。我们需要一种快速计算子矩阵“指纹”的方法。

步骤2：引入滚动哈希思想
Rabin-Karp 算法的核心是将一个窗口内的内容（字符串或矩阵）映射为一个整数哈希值，并通过滚动方式快速计算相邻窗口的哈希值，从而在 O(1) 时间内更新哈希。
对于二维矩阵，我们可以分两步进行滚动哈希：

  1. 先对每一行应用一维滚动哈希，计算每个长度为 b 的窗口的哈希值。
  2. 再在列方向上应用滚动哈希，将 a 个连续行的行哈希值组合成子矩阵哈希。

步骤3：设计二维滚动哈希函数
常用哈希函数：
对于一维数组（如一行中的连续 b 个数字），将其视为一个 b 位的二进制数（或 base 进制数），计算其数值：
hash_row = (num[0]base^{b-1} + num[1]base^{b-2} + ... + num[b-1]) mod P
其中 base 为大于最大元素值的基数（二进制中 base=2，但为减少冲突常用较大质数如 256 或 257），P 是一个大质数（如 10^9+7）。
通过滚动更新：新哈希 = ((旧哈希 - 首位数字base^{b-1}) base + 新数字) mod P，需处理负数。

步骤4：具体计算步骤
设矩阵为 matrix[m][n]，目标子矩阵大小为 a x b。

  1. 预计算 base 的幂：
    pow_base_col[b]：用于行滚动，pow_base_col[k] = base^{k} mod P。
    pow_base_row[a]：用于列滚动，pow_base_row[k] = base2^{k} mod P，其中 base2 是另一个基数，通常取另一个质数（如 131），以区分行列。

  2. 对每一行 i，计算所有长度为 b 的窗口的哈希值 row_hash[i][j]（j 从 0 到 n-b）：
    初始化第一个窗口：对 matrix[i][0..b-1] 按公式计算哈希。
    滚动更新：row_hash[i][j] = (row_hash[i][j-1] - matrix[i][j-1]pow_base_col[b-1]) base + matrix[i][j+b-1]，然后 mod P 保证非负。

  3. 在列方向上滚动计算 a x b 子矩阵哈希：
    对每个列窗口起始位置 j（0 ≤ j ≤ n-b），计算一个列哈希数组 col_hash[j][i]（i 从 0 到 m-1），其中 col_hash[j][i] = row_hash[i][j]（即第 i 行从 j 开始长为 b 的窗口哈希）。
    然后对每个 j，在 col_hash[j][0..m-1] 上做长度为 a 的窗口滚动哈希（使用 base2 和 pow_base_row）：

    • 初始化第一个窗口（行 0 到 a-1）：matrix_hash = (col_hash[j][0]pow_base_row[a-1] + col_hash[j][1]pow_base_row[a-2] + ... + col_hash[j][a-1]) mod P。
    • 将此哈希值存入全局哈希表，键为 matrix_hash，值为左上角坐标 (0, j)。
    • 滚动向下：新哈希 = ((旧哈希 - col_hash[j][上行首]pow_base_row[a-1]) base2 + col_hash[j][上行尾+1]) mod P，更新后检查哈希表。

  4. 发现重复即返回第一个匹配坐标；若全部扫描完无重复，返回 (-1, -1)。

步骤5：处理哈希冲突
由于取模，不同子矩阵可能哈希值相同（冲突）。解决方法：

  • 双哈希法：使用两组不同的 (base, P)，计算两个哈希值，同时匹配才认为相等。
  • 或当哈希值相等时，再进行一次精确比较（逐元素比较），确保结果正确。

步骤6：复杂度分析

  • 预计算幂：O(max(a, b))。
  • 计算所有行哈希：O(m*n)（每个元素参与一次行哈希计算）。
  • 计算所有子矩阵哈希：对每个 j，列方向滚动为 O(m)，总 O(m*(n-b+1)) ≈ O(m*n)。
  • 总体时间 O(mn)，空间 O(mn) 存储行哈希。
    相比 O(mna*b) 的暴力法大幅提升。

步骤7：示例演示（简化）
假设矩阵：
1 0 1
0 1 0
1 0 1
查找 2x2 重复子矩阵。
base=2, P=1e9+7（实际中 base 应取大些）。
行哈希计算（b=2）：
第0行窗口[0,1]：hash=12+0=2，窗口[1,2]：(2-12)*2+1=1。
类似得所有 row_hash。
列方向滚动（a=2）：对每个 j，将两行 row_hash 组合为矩阵哈希，发现子矩阵 [[1,0],[0,1]] 在 (0,0) 和 (1,1) 均出现，返回 (0,0)。

总结
本题通过二维滚动哈希，将子矩阵匹配的指纹计算优化到 O(1) 滚动更新，从而在 O(m*n) 时间内完成重复检测。核心是行列两次滚动哈希的配合，以及合理处理冲突。此方法可扩展至查找任意固定大小的重复模式，适用于图像处理、重复区块检测等场景。

Rabin-Karp 算法在二进制矩阵中查找重复模式 题目描述 给定一个由 0 和 1 组成的二进制矩阵（二维数组），矩阵大小为 m x n。请设计一个算法，查找在矩阵中至少重复出现两次的、尺寸为 a x b 的子矩阵（模式），并返回第一个匹配的左上角坐标。如果不存在重复子矩阵，则返回 (-1, -1)。要求算法时间复杂度尽可能高效，尤其当矩阵较大时，应避免暴力匹配。 解题过程循序渐进讲解 步骤1：理解问题与暴力解法瓶颈 我们需要在 m x n 的二进制矩阵中，找到任意一个至少出现两次的 a x b 子矩阵（a ≤ m, b ≤ n）。最直接的方法是： 枚举所有 a x b 子矩阵的左上角位置 (i, j)，其中 0 ≤ i ≤ m-a, 0 ≤ j ≤ n-b。 对每个子矩阵提取其二进制模式，存储到一个哈希表中。 当发现某个模式已存在时，即找到重复，返回第一个匹配的左上角坐标。 暴力法的瓶颈：提取每个 a x b 子矩阵需要 O(a b) 时间，总共有 (m-a+1) (n-b+1) 个子矩阵，总复杂度为 O(m n a* b)，当矩阵较大时非常慢。我们需要一种快速计算子矩阵“指纹”的方法。 步骤2：引入滚动哈希思想 Rabin-Karp 算法的核心是将一个窗口内的内容（字符串或矩阵）映射为一个整数哈希值，并通过滚动方式快速计算相邻窗口的哈希值，从而在 O(1) 时间内更新哈希。 对于二维矩阵，我们可以分两步进行滚动哈希： 先对每一行应用一维滚动哈希，计算每个长度为 b 的窗口的哈希值。 再在列方向上应用滚动哈希，将 a 个连续行的行哈希值组合成子矩阵哈希。 步骤3：设计二维滚动哈希函数 常用哈希函数： 对于一维数组（如一行中的连续 b 个数字），将其视为一个 b 位的二进制数（或 base 进制数），计算其数值： hash_ row = (num[ 0] base^{b-1} + num[ 1] base^{b-2} + ... + num[ b-1 ]) mod P 其中 base 为大于最大元素值的基数（二进制中 base=2，但为减少冲突常用较大质数如 256 或 257），P 是一个大质数（如 10^9+7）。 通过滚动更新：新哈希 = ((旧哈希 - 首位数字 base^{b-1}) base + 新数字) mod P，需处理负数。 步骤4：具体计算步骤 设矩阵为 matrix[ m][ n ]，目标子矩阵大小为 a x b。 预计算 base 的幂： pow_ base_ col[ b]：用于行滚动，pow_ base_ col[ k ] = base^{k} mod P。 pow_ base_ row[ a]：用于列滚动，pow_ base_ row[ k ] = base2^{k} mod P，其中 base2 是另一个基数，通常取另一个质数（如 131），以区分行列。 对每一行 i，计算所有长度为 b 的窗口的哈希值 row_ hash[ i][ j ]（j 从 0 到 n-b）： 初始化第一个窗口：对 matrix[ i][ 0..b-1 ] 按公式计算哈希。 滚动更新：row_ hash[ i][ j] = (row_ hash[ i][ j-1] - matrix[ i][ j-1] pow_ base_ col[ b-1]) base + matrix[ i][ j+b-1 ]，然后 mod P 保证非负。 在列方向上滚动计算 a x b 子矩阵哈希： 对每个列窗口起始位置 j（0 ≤ j ≤ n-b），计算一个列哈希数组 col_ hash[ j][ i]（i 从 0 到 m-1），其中 col_ hash[ j][ i] = row_ hash[ i][ j ]（即第 i 行从 j 开始长为 b 的窗口哈希）。 然后对每个 j，在 col_ hash[ j][ 0..m-1] 上做长度为 a 的窗口滚动哈希（使用 base2 和 pow_ base_ row）： 初始化第一个窗口（行 0 到 a-1）：matrix_ hash = (col_ hash[ j][ 0] pow_ base_ row[ a-1] + col_ hash[ j][ 1] pow_ base_ row[ a-2] + ... + col_ hash[ j][ a-1 ]) mod P。 将此哈希值存入全局哈希表，键为 matrix_ hash，值为左上角坐标 (0, j)。 滚动向下：新哈希 = ((旧哈希 - col_ hash[ j][ 上行首] pow_ base_ row[ a-1]) base2 + col_ hash[ j][ 上行尾+1 ]) mod P，更新后检查哈希表。 发现重复即返回第一个匹配坐标；若全部扫描完无重复，返回 (-1, -1)。 步骤5：处理哈希冲突 由于取模，不同子矩阵可能哈希值相同（冲突）。解决方法： 双哈希法：使用两组不同的 (base, P)，计算两个哈希值，同时匹配才认为相等。 或当哈希值相等时，再进行一次精确比较（逐元素比较），确保结果正确。 步骤6：复杂度分析 预计算幂：O(max(a, b))。 计算所有行哈希：O(m* n)（每个元素参与一次行哈希计算）。 计算所有子矩阵哈希：对每个 j，列方向滚动为 O(m)，总 O(m* (n-b+1)) ≈ O(m* n)。 总体时间 O(m n)，空间 O(m n) 存储行哈希。 相比 O(m n a* b) 的暴力法大幅提升。 步骤7：示例演示（简化） 假设矩阵： 1 0 1 0 1 0 1 0 1 查找 2x2 重复子矩阵。 base=2, P=1e9+7（实际中 base 应取大些）。 行哈希计算（b=2）： 第0行窗口[ 0,1]：hash=1 2+0=2，窗口[ 1,2]：(2-1 2)* 2+1=1。 类似得所有 row_ hash。 列方向滚动（a=2）：对每个 j，将两行 row_ hash 组合为矩阵哈希，发现子矩阵 [ [ 1,0],[ 0,1] ] 在 (0,0) 和 (1,1) 均出现，返回 (0,0)。 总结 本题通过二维滚动哈希，将子矩阵匹配的指纹计算优化到 O(1) 滚动更新，从而在 O(m* n) 时间内完成重复检测。核心是行列两次滚动哈希的配合，以及合理处理冲突。此方法可扩展至查找任意固定大小的重复模式，适用于图像处理、重复区块检测等场景。