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

字数 998 2025-11-09 12:20:55

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

题目描述
给定一个大小为 m x n 的二维字符矩阵（文本矩阵）和一个大小为 p x q 的二维字符矩阵（模式矩阵），判断模式矩阵是否在文本矩阵中出现。如果出现，返回所有匹配位置的左上角坐标。

解题过程

问题分析
- 这是一个二维模式匹配问题，暴力解法需要 O(mnp*q) 的时间复杂度。
- Rabin-Karp算法通过滚动哈希将二维匹配转化为一维哈希比较，将时间复杂度优化到平均 O(m*n)。
核心思想：滚动哈希
- 对模式矩阵计算一个哈希值，同时对文本矩阵中每个可能匹配的 p x q 子矩阵计算哈希值。
- 若哈希值匹配，再逐字符验证（避免哈希冲突）。
- 关键技巧：通过二维滚动哈希避免重复计算。
哈希函数设计
- 选择基数 base（大于字符集大小，如 256）和模数 mod（大素数，如 1e9+7）。
- 对于矩阵块，按行优先展开为一维数组，计算多项式哈希：
```
hash = (c1 * base^(k-1) + c2 * base^(k-2) + ... + ck) mod mod
```
  其中 k = p*q，ci 为字符的整数值（如 ASCII）。
预处理行哈希
- 对文本矩阵的每一行，计算长度为 q 的滑动窗口哈希（一维滚动哈希）：
  - 初始化窗口哈希：计算第一行前 q 个字符的哈希。
  - 滚动更新：窗口右移时，去掉最左字符贡献，加上新字符贡献：
```
hash_new = (hash_old - left_char * base^(q-1)) * base + new_char
```
  - 存储所有行中所有起始位置的窗口哈希值，形成二维哈希表 row_hash[i][j]，表示第 i 行从 j 开始的长度为 q 的子串哈希。
列方向滚动哈希
- 将 row_hash 视为“列向量”，对每一列 j，计算高度为 p 的窗口哈希：
  - 用 row_hash[i][j] 作为第 i 行第 j 列的“字符”，计算列方向的滚动哈希：
```
col_hash = (row_hash[i][j] * base2^(p-1) + row_hash[i+1][j] * base2^(p-2) + ...) mod mod2
```
    其中 base2 和 mod2 为另一组基数/模数，避免二维冲突。
  - 滚动计算：当窗口下移时，减去顶部行的贡献，加上新行的贡献，类似行方向滚动。
匹配验证
- 计算模式矩阵的哈希值（同样按行展开后计算）。
- 遍历文本矩阵中每个可能的位置 (i, j)，若列滚动哈希与模式哈希匹配，则逐字符比较确认。
复杂度分析
- 预处理行哈希：O(m*n)。
- 列滚动哈希：每次滚动 O(1)，总计 O(m*n)。
- 整体平均 O(mn)，最坏 O(mnpq)（当哈希冲突频繁时）。

示例代码框架（伪代码）

def rabin_karp_2d(text, pattern):
    m, n = len(text), len(text[0])
    p, q = len(pattern), len(pattern[0])
    base1, mod1 = 256, 10**9+7
    base2, mod2 = 257, 10**9+9
    
    # 计算模式矩阵哈希
    pattern_hash = 0
    for i in range(p):
        row_hash = 0
        for j in range(q):
            row_hash = (row_hash * base1 + ord(pattern[i][j])) % mod1
        pattern_hash = (pattern_hash * base2 + row_hash) % mod2
    
    # 预处理文本矩阵的行哈希
    row_hashes = [[0] * (n - q + 1) for _ in range(m)]
    for i in range(m):
        # 计算第一窗口哈希
        h = 0
        for j in range(q):
            h = (h * base1 + ord(text[i][j])) % mod1
        row_hashes[i][0] = h
        # 滚动更新
        power = pow(base1, q-1, mod1)
        for j in range(1, n - q + 1):
            h = (h - ord(text[i][j-1]) * power) % mod1
            h = (h * base1 + ord(text[i][j+q-1])) % mod1
            row_hashes[i][j] = h
    
    # 列方向滚动哈希
    results = []
    for j in range(n - q + 1):
        col_hash = 0
        power2 = pow(base2, p-1, mod2)
        # 初始化第一个窗口
        for i in range(p):
            col_hash = (col_hash * base2 + row_hashes[i][j]) % mod2
        if col_hash == pattern_hash and verify(text, pattern, 0, j):
            results.append((0, j))
        # 滚动向下
        for i in range(1, m - p + 1):
            col_hash = (col_hash - row_hashes[i-1][j] * power2) % mod2
            col_hash = (col_hash * base2 + row_hashes[i+p-1][j]) % mod2
            if col_hash == pattern_hash and verify(text, pattern, i, j):
                results.append((i, j))
    return results

def verify(text, pattern, i, j):
    # 逐字符验证匹配
    p, q = len(pattern), len(pattern[0])
    for x in range(p):
        for y in range(q):
            if text[i+x][j+y] != pattern[x][y]:
                return False
    return True

通过以上步骤，我们利用滚动哈希将二维匹配转化为高效哈希比较，显著提升了大规模矩阵模式搜索的效率。

Rabin-Karp算法在二维矩阵中查找模式题目描述给定一个大小为 m x n 的二维字符矩阵（文本矩阵）和一个大小为 p x q 的二维字符矩阵（模式矩阵），判断模式矩阵是否在文本矩阵中出现。如果出现，返回所有匹配位置的左上角坐标。解题过程问题分析这是一个二维模式匹配问题，暴力解法需要 O(m n p* q) 的时间复杂度。 Rabin-Karp算法通过滚动哈希将二维匹配转化为一维哈希比较，将时间复杂度优化到平均 O(m* n)。核心思想：滚动哈希对模式矩阵计算一个哈希值，同时对文本矩阵中每个可能匹配的 p x q 子矩阵计算哈希值。若哈希值匹配，再逐字符验证（避免哈希冲突）。关键技巧：通过二维滚动哈希避免重复计算。哈希函数设计选择基数 base（大于字符集大小，如 256）和模数 mod（大素数，如 1e9+7）。对于矩阵块，按行优先展开为一维数组，计算多项式哈希：其中 k = p* q，ci 为字符的整数值（如 ASCII）。预处理行哈希对文本矩阵的每一行，计算长度为 q 的滑动窗口哈希（一维滚动哈希）：初始化窗口哈希：计算第一行前 q 个字符的哈希。滚动更新：窗口右移时，去掉最左字符贡献，加上新字符贡献：存储所有行中所有起始位置的窗口哈希值，形成二维哈希表 row_hash[i][j] ，表示第 i 行从 j 开始的长度为 q 的子串哈希。列方向滚动哈希将 row_hash 视为“列向量”，对每一列 j，计算高度为 p 的窗口哈希：用 row_hash[i][j] 作为第 i 行第 j 列的“字符”，计算列方向的滚动哈希：其中 base2 和 mod2 为另一组基数/模数，避免二维冲突。滚动计算：当窗口下移时，减去顶部行的贡献，加上新行的贡献，类似行方向滚动。匹配验证计算模式矩阵的哈希值（同样按行展开后计算）。遍历文本矩阵中每个可能的位置 (i, j)，若列滚动哈希与模式哈希匹配，则逐字符比较确认。复杂度分析预处理行哈希：O(m* n)。列滚动哈希：每次滚动 O(1)，总计 O(m* n)。整体平均 O(m n)，最坏 O(m n p q)（当哈希冲突频繁时）。示例代码框架（伪代码）通过以上步骤，我们利用滚动哈希将二维匹配转化为高效哈希比较，显著提升了大规模矩阵模式搜索的效率。