在另一个矩阵中快速找到矩阵

Question

如果存在阶m的矩阵A [] []和阶n的另一个矩阵B [] []，使得（m> n）必须找到矩阵B [ ] []在矩阵A [] []中。

A[5][5]= 
1,2,3,4,5 
5,4,1,9,7 
2,1,7,3,4 
6,4,8,2,7 
0,2,4,5,8 

B[3][3]= 
1,9,7 
7,3,4 
8,2,7 

此矩阵B存在于A.我可以通过滑动窗口算法中TC（P^2 * N^2）O其中p = M-N + 1做到这一点。但我想用最小的时间复杂性来做到这一点。

Answer 1

可以使用Boyer-Moore string search像这样的问题：

比较从右到左。在第一行中，您将3与7进行比较。3没有出现在B的第一行，因此您可以将窗口向右移动3个元素。当您再次启动循环时，该窗口不适合A的第一行的剩余部分。这意味着你可以用2个比较来处理第一行。

在下一行，你比较1 7 1出现在B，让你在A刚够在B 1是移动你的窗口在1。

然后下一级将开始与B的右下角比较。这将比较7和7.由于7出现在B三次，你必须弄清楚如何使用Boyer-Moore类似的规则有效地移动窗口。

Answer 2

以前有一个关于堆栈溢出的摘要。希望这应该给你一些可能的算法和你可以使用的方法。 An algorithm for searching for a two dimensional m x m pattern in a two dimensional n x n text is presented。