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

题目描述：
给定一个m×n的二维矩阵（文本）和一个a×b的二维模式矩阵（a≤m, b≤n），需要在文本矩阵中查找是否存在与模式矩阵完全匹配的子矩阵。

解题过程：

1. 问题分析：

• 这是一个二维的模式匹配问题，暴力解法需要O(mna*b)的时间复杂度
• 我们可以将Rabin-Karp算法从一维扩展到二维，利用滚动哈希来优化匹配效率
• 核心思想：先计算模式矩阵的哈希值，然后在文本矩阵中滑动窗口计算子矩阵哈希值进行比较

2. 哈希函数设计：

• 对于二维矩阵，我们需要设计一个能够高效计算的哈希函数
• 常用的方法是使用多项式哈希：hash = Σ(matrix[i][j] * base1^i * base2^j) mod prime
• 其中base1和base2是基数，prime是大质数

3. 具体步骤：

步骤1：预处理模式矩阵的哈希值

def compute_pattern_hash(pattern, base1, base2, prime):
    a, b = len(pattern), len(pattern[0])
    hash_val = 0
    power1 = 1
    
    for i in range(a):
        power2 = 1
        row_hash = 0
        for j in range(b):
            row_hash = (row_hash + pattern[i][j] * power2) % prime
            power2 = (power2 * base2) % prime
        hash_val = (hash_val + row_hash * power1) % prime
        power1 = (power1 * base1) % prime
    
    return hash_val

步骤2：预处理文本矩阵的行哈希

• 为了提高效率，我们先计算文本矩阵每行的滚动哈希

def precompute_row_hashes(matrix, b, base2, prime):
    m, n = len(matrix), len(matrix[0])
    row_hashes = [[0] * (n - b + 1) for _ in range(m)]
    
    for i in range(m):
        # 计算第一窗口的哈希
        hash_val = 0
        power = 1
        for j in range(b):
            hash_val = (hash_val + matrix[i][j] * power) % prime
            power = (power * base2) % prime
        
        row_hashes[i][0] = hash_val
        
        # 滚动计算后续窗口
        base_power = pow(base2, b-1, prime)
        for j in range(1, n - b + 1):
            hash_val = (hash_val - matrix[i][j-1]) // base2
            hash_val = (hash_val + matrix[i][j+b-1] * base_power) % prime
            row_hashes[i][j] = hash_val
    
    return row_hashes

步骤3：在列方向上进行滚动哈希

def rabin_karp_2d(matrix, pattern):
    m, n = len(matrix), len(matrix[0])
    a, b = len(pattern), len(pattern[0])
    prime = 10**9 + 7
    base1, base2 = 257, 263
    
    # 计算模式矩阵哈希
    pattern_hash = compute_pattern_hash(pattern, base1, base2, prime)
    
    # 预处理行哈希
    row_hashes = precompute_row_hashes(matrix, b, base2, prime)
    
    # 在列方向滚动计算
    for j in range(n - b + 1):
        # 计算第一窗口的列哈希
        col_hash = 0
        power = 1
        for i in range(a):
            col_hash = (col_hash + row_hashes[i][j] * power) % prime
            power = (power * base1) % prime
        
        if col_hash == pattern_hash:
            # 验证是否真正匹配（避免哈希冲突）
            if verify_match(matrix, pattern, 0, j):
                return True
        
        # 滚动计算后续窗口
        base_power = pow(base1, a-1, prime)
        for i in range(1, m - a + 1):
            col_hash = (col_hash - row_hashes[i-1][j]) // base1
            col_hash = (col_hash + row_hashes[i+a-1][j] * base_power) % prime
            
            if col_hash == pattern_hash:
                if verify_match(matrix, pattern, i, j):
                    return True
    
    return False

步骤4：验证函数（处理哈希冲突）

def verify_match(matrix, pattern, start_i, start_j):
    a, b = len(pattern), len(pattern[0])
    for i in range(a):
        for j in range(b):
            if matrix[start_i + i][start_j + j] != pattern[i][j]:
                return False
    return True

4. 时间复杂度分析：

• 预处理行哈希：O(m*n)
• 列方向滚动哈希：O(m*n)
• 总体时间复杂度：O(mn)，比暴力解法的O(mnab)优化很多
• 空间复杂度：O(m*n)用于存储行哈希

5. 应用场景：

• 图像处理中的模板匹配
• 文档扫描中的字符识别
• 生物信息学中的基因序列匹配

这个算法通过将二维问题转化为一维的滚动哈希计算，巧妙地利用了Rabin-Karp算法的优势，在保持准确性的同时大幅提高了匹配效率。