二维字符矩阵匹配问题：判断子矩阵存在及起始位置查询

嘿，我来帮你搞定这个二维矩阵匹配的问题，下面从问题解析到高效实现一步步给你讲清楚：

问题明确 #

先把需求再理一遍：

给定一个N×N（2≤N≤800）的大型字符网格，以及一个K×K（2≤K≤100）的小型字符网格，需要完成两个任务：

1. 判断大矩阵里是否存在和小矩阵完全一致的子矩阵；
2. 如果匹配成功，返回小矩阵左上角在大矩阵中的0-based起始坐标。

举个实际例子：

• 大矩阵（N=3）：

  abc
  abd
  aaa
  

• 小矩阵（K=2）：

  bd
  aa
  

• 结果：匹配成立，起始位置是(1,1)

解决思路 #

思路1：暴力匹配（直观但效率有限） #

这是最容易想到的方法，适合小数据量场景，但面对N=800、K=100的情况可能会超时，不过可以先理解基础逻辑：

• 遍历大矩阵里所有可能的起始位置(i,j)，这里i的范围是0 ≤ i ≤ N-K，j是0 ≤ j ≤ N-K（保证子矩阵不会超出大矩阵边界）；
• 对每个起始位置，逐行逐列对比大矩阵从(i,j)开始的K×K子矩阵和小矩阵的每一个字符；
• 一旦找到完全匹配的子矩阵，直接返回(i,j)；要是遍历完所有位置都没匹配到，就说明不包含。

缺点：时间复杂度是O((N-K+1)^2 * K^2)，当N=800、K=100时，计算量接近50亿次操作，大概率会超时，所以更推荐下面的优化方法。

思路2：二维前缀哈希法（高效首选） #

这个方法通过把矩阵转化为哈希值，把矩阵匹配变成哈希值的比对，能大幅提升效率：

步骤1：预处理哈希值

我们可以用**滚动哈希（多项式哈希）**来处理二维矩阵：

1. 先算每行的哈希：把每行的字符序列当成一个“数字串”，比如把a映射为0，b映射为1，选一个大质数作为基数（比如911382629），每行的哈希值就是c0 * base^(K-1) + c1 * base^(K-2) + ... + c(K-1)；
2. 再基于行哈希算列哈希：把每行的哈希值当成新的“元素”，再对每一列做同样的哈希计算，这样大矩阵里任意一个K×K子矩阵的哈希值都能在O(1)时间内得到；
3. 预先算出小矩阵的整体哈希值。

步骤2：比对哈希值

• 遍历大矩阵里所有可能的K×K子矩阵，计算它的哈希值和小矩阵的哈希值对比；
• 为了避免极低概率的哈希冲突，当哈希值相同时，再逐元素验证一次（保险起见）；
• 找到匹配的子矩阵就返回起始坐标，否则返回匹配失败。

优点：预处理时间是O(N² + K²)，比对时间是O((N-K+1)²)，对于N=800的情况，总计算量大概110万次操作，效率拉满。

示例拆解 #

拿题目里的例子来走一遍流程：

• 先把字符映射成数字：a=0，b=1，c=2，d=3，选基数base=26；
• 大矩阵的行哈希：
  第一行abc：0*26² + 1*26 + 2 = 28；
  第二行abd：0*26² + 1*26 + 3 = 29；
  第三行aaa：0*26² + 0*26 + 0 = 0；
• 大矩阵中以(1,1)为起点的2×2子矩阵：
  子矩阵的两行是bd（哈希1*26 +3=29）和aa（哈希0*26+0=0）；
  对这两个行哈希算列哈希：29*26 + 0 =754；
• 小矩阵的行哈希是bd=29、aa=0，列哈希也是754，哈希值一致，再逐元素验证确实匹配，所以返回(1,1)。

注意要点 #

• 哈希冲突：可以用双哈希方案，也就是用两个不同的基数和模数，同时比对两个哈希值，几乎能完全避免冲突；
• 字符映射：要统一把字符转成数字，比如用ord(c) - ord('a')，确保每个字符对应唯一数值；
• 边界检查：遍历起始位置时，一定要保证i+K ≤ N和j+K ≤ N，别越界访问数组。

内容的提问来源于stack exchange，提问作者Sazzad Hissain Khan