使用大而密集的2D矩阵快速计算2D子矩阵？
在较大的密集矩阵中计算子矩阵的好算法是什么？ 如果我有一行数据，我可以使用后缀树，但我不确定是否将后缀树推广到更高维度是完全简单或最好的方法。
思考？
我的天真解决方案是索引密集矩阵的第一个元素并消除全矩阵搜索，只提供了对全矩阵扫描的适度改进。
解决这个问题的最佳方法是什么？
Example: Input: Full matrix: 123 212 421 Search matrix: 12 21 Output: 2 该子矩阵在全矩阵中出现两次 ，因此输出为2.完整矩阵可以是1000×1000，但是，搜索矩阵大到100×100（可变大小），我需要处理多个搜索矩阵。一排。 因此，这个问题的蛮力非常低效，无法满足几个矩阵的亚秒搜索时间。
对于算法课程，我曾经做过一个练习，其中Rabin-Karp字符串搜索算法必须稍微扩展，以您描述的方式搜索匹配的二维子矩阵。
我想如果你花时间去理解维基百科上描述的算法，那么将它扩展到二维的自然方式将是你很清楚的。 实质上，您只需在矩阵上进行多次传递，一次沿着一列爬行。 有一些小技巧可以让时间复杂度尽可能低，但你可能根本不需要它们。
在N×N矩阵中搜索M×M矩阵，这种方法应该给你一个O（N²·M）算法。 有了技巧，我相信它可以精炼到O（N²）。
计算手册的算法和理论建议什么是N ^ 2 *日志（字母大小）解决方案。 给定要搜索的子矩阵，首先要对其行进行重复数据删除。 现在请注意，如果您逐行搜索大矩阵，则最多一个已删除的行可以出现在任何位置。 使用Aho-Corasick在时间上搜索N ^ 2 * log（字母大小）并在大矩阵中的每个单元处向下记录空或者子矩阵的匹配行的标识符。 现在再次使用Aho-Corasick搜索行匹配矩阵的列，并发出匹配信号，其中所有行都存在于彼此之下。
这听起来类似于模板匹配。 如果有动机，您可以使用FFT转换原始数组，并从powershell搜索中删除日志。 （N log（M））代替（N M）
我没有现成的答案，但这是我将如何开始：
– 您希望快速查找，您可以花多少（时间）构建索引结构？ 当蛮力不够快时，你需要索引。
– 您对未告诉我们的数据了解多少？ 所有矩阵中的所有值都是单位整数吗？
– 如果它们是单位数整数（或者您可以表示为单个字符或索引值的任何其他内容），请考虑线性化2D结构。 一种方法是沿着从左上角到左下角的对角线读取矩阵，从左上角到右下角扫描。 难以用文字解释，但阅读矩阵：
1234 5678 90ab cdef
如125369470c8adbef
（得到它？）
现在，您可以将超级矩阵索引到您的速度和空间要求所需的任何深度; 在我的示例键1253中…指向元素（1,1），键abef指向元素（3,3）。 不确定这是否适合您，您将不得不使用解决方案的参数。 选择您喜欢的存储键值对的方法：哈希，列表，甚至在事情变得疯狂时在索引中构建一些索引。
问候
标记