在大矩阵中找到矩阵

Question

我有一个非常大的n*m矩阵S.我想有效地确定F内部是否存在子矩阵S.大矩阵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-bit整数.我只能想到使用蛮力方法来查找是否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

如果要多次查询相同的大矩阵和相同大小的子矩阵。有很多解决方案来预处理大矩阵。

这里有一个类似（甚至相同）的问题。

在 MXN 矩阵中查找 amxn 子矩阵的最快方法