c++ - 在大矩阵中找到一个矩阵

Question

我有一个非常大的 n*m 矩阵 S。我想有效地确定在 S 内部是否存在子矩阵 F。大矩阵 S 的大小可以达到 500*500。

为了澄清，考虑以下几点:

S = 1 2 3 
    4 5 6
    7 8 9

F1 = 2 3 
     5 6

F2 = 1 2 
     4 6

在这种情况下:

• F1 在 S
里面
• F2 不在 S
内

矩阵中的每个元素都是一个32 位 整数。我只能想到使用暴力法来查找F 是否是S 的子矩阵。我用谷歌搜索找到了一种有效的算法，但我找不到任何东西。

是否有一些算法或原理可以更快地完成它？ (或者可能是一些优化蛮力方法的方法？)

PS统计数据

A total of 8 S
On average, each S will be matched against about 44 F.
The probability of success match (i.e. F appears in a S) is 
19%.

Answer 1

它涉及对矩阵进行预处理。这会占用大量内存，但在计算时间方面应该会更好。

• 检查前检查子矩阵的大小是否小于矩阵的大小。
• 在构建矩阵时，构建一个结构，将矩阵中的值映射到矩阵中的 (x,y) 位置数组。这将允许您检查是否存在候选可能存在的子矩阵。您将使用子矩阵中 (0,0) 处的值，并获取该值在较大矩阵中的可能位置。如果职位列表为空，则您没有候选人，因此子矩阵不存在。这是一个开始(然而，更有经验的人可能认为这是一种幼稚的方法)。