Rabin-Karp 算法在二进制矩阵中查找重复模式
字数 2484 2025-12-08 13:20:26

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

题目描述

给定一个大小为 m x n 的二进制矩阵 matrix（元素为 0 或 1），以及一个大小为 p x q 的目标二进制矩阵 pattern（p <= m, q <= n）。要求设计一个算法，在 matrix 中高效地查找所有与 pattern 完全相同的子矩阵，并返回每个匹配子矩阵的左上角坐标。你的算法需要利用哈希技术（特别是滚动哈希）来优化查找效率。

解题思路

  1. 暴力法的问题：
    若直接逐行逐列比较每个 p x q 的子矩阵，时间复杂度为 O(m * n * p * q)，当矩阵较大时效率很低。
  2. 引入滚动哈希：
    采用 Rabin-Karp 算法的思想，先对矩阵的行和列分别计算哈希值，通过滚动方式快速计算子矩阵的哈希值，从而将比较时间降至常数。
  3. 核心步骤：
    • 对 matrix 的每一行计算长度为 q 的窗口的滚动哈希。
    • 对第一步得到的列哈希值（即每个子矩阵的列哈希序列）再计算长度为 p 的窗口的滚动哈希，得到每个 p x q 子矩阵的整体哈希。
    • 计算 pattern 的哈希值，与子矩阵哈希值比较，匹配时再进行逐元素验证（避免哈希冲突）。

详细步骤

步骤 1：选择哈希函数

滚动哈希常用多项式哈希：
对于序列 a₁, a₂, ..., a_k，哈希值 H = (a₁ * d^{k-1} + a₂ * d^{k-2} + ... + a_k) mod M，其中 d 为基数（如 256），M 为大素数（如 10^9+7）。
二进制矩阵中，元素为 0/1，可直接作为系数。

步骤 2：计算 pattern 的哈希值

  • 先计算 pattern 每一行的哈希值（长度为 q）：
    rowHashPattern[i] = hash(pattern[i][0..q-1])，i = 0..p-1。
  • 再将 rowHashPattern 视为列序列（长度为 p），计算整体哈希：
    hashPattern = hash(rowHashPattern[0..p-1])。

步骤 3：对 matrix 预处理行滚动哈希

对于 matrix 的每一行 i（共 m 行）：

  • 计算该行第一个长度为 q 的窗口的哈希值：
    rowHash[i][0] = hash(matrix[i][0..q-1])。
  • 使用滚动哈希向右滑动窗口，计算 rowHash[i][j]（j = 0..n-q）：
    若已知 rowHash[i][j]，则
    rowHash[i][j+1] = (rowHash[i][j] - matrix[i][j] * d^{q-1}) * d + matrix[i][j+q]（所有运算取模 M）。
    这样每行计算所有窗口的哈希值时间复杂度为 O(n)。

步骤 4：对列方向计算子矩阵哈希

将 rowHash 视为一个二维数组 rowHash[i][j]，表示以 (i, j) 为左上角、宽度为 q 的行片段的哈希值。
现在要找到高度为 p 的子矩阵，即对每个列 j，在垂直方向计算长度为 p 的窗口哈希：

  • 对于列 j，取序列 rowHash[0][j], rowHash[1][j], ..., rowHash[m-1][j]。
  • 计算该序列第一个长度为 p 的窗口哈希值：
    colHash[0][j] = hash(rowHash[0..p-1][j])。
  • 使用滚动哈希向下滑动窗口，计算 colHash[i][j]（i = 0..m-p, j = 0..n-q）：
    若已知 colHash[i][j]，则
    colHash[i+1][j] = (colHash[i][j] - rowHash[i][j] * d^{p-1}) * d + rowHash[i+p][j]（模 M）。
    得到的 colHash[i][j] 即为以 (i, j) 为左上角的 p x q 子矩阵的哈希值。

步骤 5：匹配与验证

  • 遍历所有 i = 0..m-p, j = 0..n-q，比较 colHash[i][j] 与 hashPattern。
  • 若哈希值相等，则进行逐元素验证（因哈希可能冲突），确认子矩阵与 pattern 完全相同。
  • 验证通过后，记录坐标 (i, j)。

复杂度分析

  • 时间复杂度：
    预处理行哈希：O(m * n)
    计算列哈希：O((m-p+1) * n) ≈ O(m * n)
    比较与验证：最坏 O(m * n * p * q)，但实际因哈希匹配较少，接近 O(m * n)。
  • 空间复杂度：
    存储 rowHash 和 colHash：O(m * n)。

示例演示

假设：

matrix = [[1,0,1],
          [0,1,0],
          [1,0,1]]
pattern = [[1,0],
           [0,1]]
  1. 计算 pattern 哈希：
    行哈希：第0行 hash([1,0])，第1行 hash([0,1])，再计算列哈希。
  2. 对 matrix 计算行滚动哈希（窗口长 q=2）：
    如第0行：hash([1,0])，滚动到 hash([0,1])。
  3. 对列计算滚动哈希（窗口长 p=2）：
    以列 j=0 为例，序列为 rowHash[0][0], rowHash[1][0], rowHash[2][0]，计算第一个窗口哈希（对应子矩阵左上角 (0,0)）。
  4. 匹配发现 (0,0) 和 (1,1) 的哈希与 pattern 相同，验证后确认匹配。

关键点

  • 滚动哈希允许在常数时间内更新窗口哈希。
  • 二维滚动需先横向再纵向（或先纵向再横向），两次滚动实现子矩阵哈希快速计算。
  • 需处理哈希冲突：匹配后必须进行逐元素验证。

通过这种方法，我们能将子矩阵匹配的平均时间复杂度优化至接近线性，适合处理较大的二进制矩阵。

Rabin-Karp 算法在二进制矩阵中查找重复模式 题目描述 给定一个大小为 m x n 的二进制矩阵 matrix （元素为 0 或 1 ），以及一个大小为 p x q 的目标二进制矩阵 pattern （ p <= m , q <= n ）。要求设计一个算法，在 matrix 中高效地查找所有与 pattern 完全相同的子矩阵，并返回每个匹配子矩阵的左上角坐标。你的算法需要利用哈希技术（特别是滚动哈希）来优化查找效率。 解题思路 暴力法的问题 ： 若直接逐行逐列比较每个 p x q 的子矩阵，时间复杂度为 O(m * n * p * q) ，当矩阵较大时效率很低。 引入滚动哈希 ： 采用 Rabin-Karp 算法的思想，先对矩阵的行和列分别计算哈希值，通过滚动方式快速计算子矩阵的哈希值，从而将比较时间降至常数。 核心步骤 ： 对 matrix 的每一行计算长度为 q 的窗口的滚动哈希。 对第一步得到的列哈希值（即每个子矩阵的列哈希序列）再计算长度为 p 的窗口的滚动哈希，得到每个 p x q 子矩阵的整体哈希。 计算 pattern 的哈希值，与子矩阵哈希值比较，匹配时再进行逐元素验证（避免哈希冲突）。 详细步骤 步骤 1：选择哈希函数 滚动哈希常用多项式哈希： 对于序列 a₁, a₂, ..., a_k ，哈希值 H = (a₁ * d^{k-1} + a₂ * d^{k-2} + ... + a_k) mod M ，其中 d 为基数（如 256）， M 为大素数（如 10^9+7）。 二进制矩阵中，元素为 0/1，可直接作为系数。 步骤 2：计算 pattern 的哈希值 先计算 pattern 每一行的哈希值（长度为 q ）： rowHashPattern[i] = hash(pattern[i][0..q-1]) ， i = 0..p-1 。 再将 rowHashPattern 视为列序列（长度为 p ），计算整体哈希： hashPattern = hash(rowHashPattern[0..p-1]) 。 步骤 3：对 matrix 预处理行滚动哈希 对于 matrix 的每一行 i （共 m 行）： 计算该行第一个长度为 q 的窗口的哈希值： rowHash[i][0] = hash(matrix[i][0..q-1]) 。 使用滚动哈希向右滑动窗口，计算 rowHash[i][j] （ j = 0..n-q ）： 若已知 rowHash[i][j] ，则 rowHash[i][j+1] = (rowHash[i][j] - matrix[i][j] * d^{q-1}) * d + matrix[i][j+q] （所有运算取模 M ）。 这样每行计算所有窗口的哈希值时间复杂度为 O(n) 。 步骤 4：对列方向计算子矩阵哈希 将 rowHash 视为一个二维数组 rowHash[i][j] ，表示以 (i, j) 为左上角、宽度为 q 的行片段的哈希值。 现在要找到高度为 p 的子矩阵，即对每个列 j ，在垂直方向计算长度为 p 的窗口哈希： 对于列 j ，取序列 rowHash[0][j], rowHash[1][j], ..., rowHash[m-1][j] 。 计算该序列第一个长度为 p 的窗口哈希值： colHash[0][j] = hash(rowHash[0..p-1][j]) 。 使用滚动哈希向下滑动窗口，计算 colHash[i][j] （ i = 0..m-p , j = 0..n-q ）： 若已知 colHash[i][j] ，则 colHash[i+1][j] = (colHash[i][j] - rowHash[i][j] * d^{p-1}) * d + rowHash[i+p][j] （模 M ）。 得到的 colHash[i][j] 即为以 (i, j) 为左上角的 p x q 子矩阵的哈希值。 步骤 5：匹配与验证 遍历所有 i = 0..m-p , j = 0..n-q ，比较 colHash[i][j] 与 hashPattern 。 若哈希值相等，则进行逐元素验证（因哈希可能冲突），确认子矩阵与 pattern 完全相同。 验证通过后，记录坐标 (i, j) 。 复杂度分析 时间复杂度： 预处理行哈希： O(m * n) 计算列哈希： O((m-p+1) * n) ≈ O(m * n) 比较与验证：最坏 O(m * n * p * q) ，但实际因哈希匹配较少，接近 O(m * n) 。 空间复杂度： 存储 rowHash 和 colHash ： O(m * n) 。 示例演示 假设： 计算 pattern 哈希： 行哈希：第0行 hash([1,0]) ，第1行 hash([0,1]) ，再计算列哈希。 对 matrix 计算行滚动哈希（窗口长 q=2 ）： 如第0行： hash([1,0]) ，滚动到 hash([0,1]) 。 对列计算滚动哈希（窗口长 p=2 ）： 以列 j=0 为例，序列为 rowHash[0][0] , rowHash[1][0] , rowHash[2][0] ，计算第一个窗口哈希（对应子矩阵左上角 (0,0) ）。 匹配发现 (0,0) 和 (1,1) 的哈希与 pattern 相同，验证后确认匹配。 关键点 滚动哈希允许在常数时间内更新窗口哈希。 二维滚动需先横向再纵向（或先纵向再横向），两次滚动实现子矩阵哈希快速计算。 需处理哈希冲突：匹配后必须进行逐元素验证。 通过这种方法，我们能将子矩阵匹配的平均时间复杂度优化至接近线性，适合处理较大的二进制矩阵。