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

题目描述
给定一个 m×n 的二维字符矩阵（文本矩阵）和一个 a×b 的二维字符矩阵（模式矩阵），其中 a ≤ m 且 b ≤ n。请设计一个算法，判断模式矩阵是否在文本矩阵中出现。要求利用哈希算法优化匹配效率。

解题过程

1. 问题分析
这是一个二维的模式匹配问题。最直观的方法是逐个位置比较，时间复杂度为 O((m-a+1)×(n-b+1)×a×b)，当矩阵较大时效率很低。

Rabin-Karp 算法的核心思想是：通过哈希值快速判断是否可能匹配，只有哈希值匹配时才进行详细的逐字符比较。

2. 一维Rabin-Karp回顾
首先回忆一维情况下的Rabin-Karp：

• 计算模式串的哈希值
• 计算文本中每个长度为m的滑动窗口的哈希值
• 当哈希值匹配时，进行精确比较
• 使用滚动哈希，使每次滑动时哈希值可以快速更新

3. 扩展到二维的思路
将二维问题转化为一维处理：

• 先计算每一行的滚动哈希
• 然后在列方向上再次使用滚动哈希
• 这样就能高效计算每个a×b子矩阵的哈希值

4. 具体实现步骤

步骤1：预处理行哈希
对于文本矩阵的每一行，计算所有长度为b的窗口的哈希值：

# 使用多项式滚动哈希
base = 131  # 选择一个质数作为基数
mod = 10**9 + 7  # 大质数取模

# 计算第i行所有长度为b的窗口哈希
row_hashes = [[0]*(n-b+1) for _ in range(m)]
for i in range(m):
    # 计算第一个窗口的哈希
    hash_val = 0
    for j in range(b):
        hash_val = (hash_val * base + ord(text[i][j])) % mod
    row_hashes[i][0] = hash_val
    
    # 滚动计算后续窗口
    for j in range(1, n-b+1):
        # 移除左边字符，加入右边字符
        left_char = ord(text[i][j-1])
        right_char = ord(text[i][j+b-1])
        # 计算base^(b-1)的幂，用于移除最左边的字符
        power = pow(base, b-1, mod)
        hash_val = ((hash_val - left_char * power) * base + right_char) % mod
        row_hashes[i][j] = hash_val

步骤2：在列方向计算二维哈希
现在我们有每行的窗口哈希，接下来在列方向计算a×b子矩阵的哈希：

# 计算模式矩阵的哈希
pattern_hash = 0
for i in range(a):
    row_hash = 0
    for j in range(b):
        row_hash = (row_hash * base + ord(pattern[i][j])) % mod
    pattern_hash = (pattern_hash * base + row_hash) % mod

# 计算文本中每个a×b子矩阵的哈希
for col in range(n-b+1):  # 列方向的起始位置
    # 计算第一个窗口的列哈希
    col_hash = 0
    for i in range(a):
        col_hash = (col_hash * base + row_hashes[i][col]) % mod
    
    # 检查第一个窗口
    if col_hash == pattern_hash:
        # 进行精确比较（避免哈希冲突）
        if exact_match(text, pattern, 0, col, a, b):
            return True
    
    # 滚动计算后续窗口
    base_power = pow(base, a-1, mod)
    for i in range(1, m-a+1):
        # 移除最上面一行的哈希，加入新一行的哈希
        top_row_hash = row_hashes[i-1][col]
        bottom_row_hash = row_hashes[i+a-1][col]
        col_hash = ((col_hash - top_row_hash * base_power) * base + bottom_row_hash) % mod
        
        if col_hash == pattern_hash:
            if exact_match(text, pattern, i, col, a, b):
                return True

步骤3：精确比较函数
由于可能存在哈希冲突，需要验证实际匹配：

def exact_match(text, pattern, start_row, start_col, a, b):
    for i in range(a):
        for j in range(b):
            if text[start_row + i][start_col + j] != pattern[i][j]:
                return False
    return True

5. 算法复杂度分析

• 时间复杂度：平均O(m×n)，最坏O(m×n×a×b)
• 空间复杂度：O(m×n)存储行哈希
• 通过合理的基数和模数选择，可以极大降低哈希冲突概率

6. 优化考虑

• 使用双重哈希（两个不同的基数和模数）进一步减少冲突
• 对于非常大的矩阵，可以考虑分块处理
• 在实际应用中，通常哈希匹配的成功率很高，精确比较的次数很少

这种二维Rabin-Karp算法在大规模文本搜索、图像匹配等领域有重要应用。