使用大而密集的 2D 矩阵快速计算 2D 子矩阵？

Question

在较大的密集矩阵中计算子矩阵的好算法是什么？如果我只有一行数据，我可以使用后缀树，但我不确定将后缀树泛化到更高维度是完全直接的还是这里的最佳方法。

想法？

我对密集矩阵的第一个元素进行索引并消除全矩阵搜索的天真解决方案仅提供了对全矩阵扫描的适度改进。

解决这个问题的最佳方法是什么？

Example:

Input:

Full matrix:
123
212
421

Search matrix:
12  
21  

Output:
2

这个子矩阵在完整矩阵中出现两次，所以输出是 2。完整矩阵可能是 1000x1000，但是，搜索矩阵大到 100x100（可变大小），我需要处理多个搜索矩阵一排。因此，这个问题的蛮力效率太低，无法满足我对几个矩阵的亚秒级搜索时间。

Answer 1

对于算法课程，我曾经做过一个练习，其中必须稍微扩展Rabin-Karp字符串搜索算法，以按照您描述的方式搜索匹配的二维子矩阵。

\n\n

我认为，如果您花时间理解维基百科上描述的算法，那么您就会清楚将其扩展到二维的自然方法。本质上，您只需在矩阵上进行几次遍历，一次沿着一列爬​​行。有一些小技巧可以使时间复杂度尽可能低，但您可能根本不需要它们。

\n\n

在 N\xc3\x97N 矩阵中搜索 M\xc3\x97M 矩阵，这种方法应该为您提供 O(N\xc2\xb2\xe2\x8b\x85M) 算法。通过技巧，我相信它可以细化为 O(N\xc2\xb2)。

\n