在另一個矩陣中快速找到矩陣

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。