Python矩阵模式匹配实现：如何在大矩阵中查找指定子矩阵位置

核心实现逻辑 #

• 首先确定遍历边界：大矩阵尺寸为M×N，模式矩阵尺寸为P×Q，行维度的遍历上限为M-P，列维度的遍历上限为N-Q，保证每次提取的子矩阵尺寸和模式完全匹配，不会出现索引越界
• 逐一枚举所有可能的子矩阵左上角坐标(i,j)，逐元素对比子矩阵与模式矩阵：
  • 子矩阵的(x,y)位置元素对应大矩阵的matrix[i+x][j+y]，和pattern[x][y]做全等校验
  • 任意元素不匹配则立刻终止当前子矩阵的校验，跳转至下一个左上角坐标
  • 所有元素完全匹配则返回当前坐标，若遍历完所有位置都无匹配则返回无结果

可直接运行的Python实现 #

def find_pattern(matrix: list[list[int]], pattern: list[list[int]]) -> int | None:
    # 获取矩阵尺寸
    M = len(matrix)
    N = len(matrix[0]) if M else 0
    P = len(pattern)
    Q = len(pattern[0]) if P else 0

    # 不符合前置条件直接返回
    if P >= M or Q >= N:
        return None

    # 遍历所有合法的左上角坐标
    for i in range(M - P + 1):
        for j in range(N - Q + 1):
            is_match = True
            # 逐元素对比
            for x in range(P):
                for y in range(Q):
                    if matrix[i + x][j + y] != pattern[x][y]:
                        is_match = False
                        break
                if not is_match:
                    break
            if is_match:
                # 按示例要求返回匹配位置的行索引，可根据需求修改为返回(i,j)完整坐标
                return i
    return None

# 测试用例
if __name__ == "__main__":
    matrix = [
        [1,0,0],
        [0,1,0],
        [0,0,0]
    ]
    pattern = [
        [1,0],
        [0,1]
    ]
    result = find_pattern(matrix, pattern)
    if result is not None:
        print(f"Pattern found at index {result}")
    else:
        print("Pattern not found")

运行上述代码输出结果为Pattern found at index 0，和预期一致。

优化方案（适配大尺寸矩阵场景） #

如果需要处理的矩阵尺寸很大，暴力逐元素对比的O(MNPQ)时间复杂度性能不足，可以使用二维Rabin-Karp滚动哈希算法优化：

• 第一步对大矩阵每行的长度为Q的滑动窗口计算哈希值，生成新的哈希矩阵
• 第二步对哈希矩阵每列的长度为P的滑动窗口计算哈希值，得到所有P×Q子矩阵的哈希值
• 预先计算模式矩阵的哈希值，和子矩阵哈希值直接对比即可，整体时间复杂度可降到O(MN + PQ)

内容的提问来源于stack exchange，提问作者Allen