有没有办法将子矩阵与更大的矩阵匹配？

Question

这是一个二维矩阵匹配问题。给定一个较大的矩阵，找出一个较小的矩阵，它与大矩阵中的数字相匹配。到这里还很简单，因为我可以使用Rabin Karp匹配来找到子矩阵，但是这里有一个问题，子矩阵中可以有字母，字母表应该在整个子矩阵匹配过程中匹配相同的数字。例如：

大矩阵：

[
      [2, 5, 2, 5, 2],
      [5, 1, 5, 2, 3],
      [1, 5, 2, 5, 4]
]

子矩阵：

[
      [5, a],
      [a, e]
]

这应该将a与相同的数字相匹配，e可以是任意数字。所以这里的比赛是在(1, 0)，因为5在(1, 0)和a=1在[(1,1), (2,0)]和e=5上匹配。

编辑：添加了约束

制约因素：

1 <=长度(大矩阵) <= 50

1 <=长度(大矩阵中的任意行) <= 50

1 <=长度(子矩阵) <= min(董事会矩阵)，长度( Matrixrow大小)

大矩阵只包含数字，但子矩阵可以包含字母或数字。条件：

1. 任何数字都应该对应于大矩阵中的同一位数。

1. 任何字母都应该对应一个数字，在整个子矩阵中应该对应相同的数字。

1. 任何两个不同的字母都应该对应于两个不同的数字。也就是说，没有两个字符可以有相同的数字映射。

Answer 1

如果矩阵包含个位数，且变量的数量不太大，则可以预先计算a和e的所有可能值的子矩阵散列(在本例中为100 )，并将它们存储在数据结构中，如散列集。然后，当您计算滚动哈希作为Rabin匹配算法的一部分时，您可以检查哈希是否在每一步的哈希集中。这个检查应该是O(1)。

Answer 2

大声思考：

预处理要列出的模式

• 数字条目；

• 按等号分组的字母，可能将单数放在一边。

仅在数字上执行模式搜索，使用蛮力(或者使用不关心符号的矩阵搜索?)。对于每一个候选人来说，

• 检查字母赋值是否兼容(条件2.)，不需要用于单件，

• 检查赋值是否唯一(条件3.).