我現在正面臨一個問題，我需要計算某個MxM矩陣出現在NxN內部的時間的數量（這個矩陣應該大於第一個）。如何做到這一點的任何提示？我要用C語言來實現它，並且沒有選擇來改變它。計算一個大矩陣內出現的矩陣的算法
修訂1
大家好，我真的很想說，感謝對此事所有的答案和意見。我應該告訴你，經過數小時的努力，我們得出的解決方案並不完全像Boyer-Moore方法，而是我自己的算法。我打算一旦測試完成後發佈它。現在，這些解決方案正在適應於使用帶有C庫MPI的大學集羣進行速度優化的平行化。
嗯，聽起來像是一個二維版本的字符串匹配。我想知道是否有Boyer-Moore的2D版本？
A Boyer-Moore Approach for Two-Dimensional Matching
啊，顯然存在。 :-)立即來考慮
一種方法：
對待大矩陣的N * N「字符」 a線性串和小矩陣作爲長度的線性正則表達式（M + 1） * M在每個「行」的前M個位置中具有「文字字符」，並且在每行的剩餘位置中等同於.{N-M}。將正則表達式編譯爲DFA並運行。
找到所有匹配的時間是O（N * N）。我懷疑有更奇妙的算法可以工作（fancier 1-d子字符串搜索算法的改編），但這個並不算太壞。
最近，已經開發了用於構建2D後綴樹的快速算法。這些可以被用來找到一個更大的矩陣在時間無關的更大的矩陣大小的任何方塊子矩陣：
你可能需要一個用戶看到那些報紙。
我也發現了這個免費的之一，它描述了隨機構造算法是預期線性時間：
我希望構建一個2D後綴樹和搜索如果您需要在單個矩陣中搜索許多不同的子矩陣，速度會更快，但如果您每次都在不同的矩陣中搜索，它可能會比2D Boyer-Moore慢。
「與大矩陣的大小無關」絕對是錯誤的。考慮在NxN矩陣中搜索1x1子矩陣。沒有辦法在少於N^2次的時間內找到它。也許你的意思是獨立於小矩陣的大小......？ – 2011-06-07 15:16:56
@R .:你忘記了索引構建時間，當然這需要查看所有NxN元素。一旦建立起來，2D後綴樹就可以讓您在大約一個步驟中搜索NxN矩陣中的1x1子矩陣，就像1D後綴樹一樣，您可以在大約6個步驟中找到所有莎士比亞作品中是否出現「香蕉」 。 （這是查找單個事件的時間複雜度 - 列出所有事件需要更多時間。） – 2011-06-08 06:24:24
你到目前爲止想到了什麼？ – 2011-06-06 23:10:04
@Oli_Charlesworth @Oli_Charlesworth我正在考慮線性矩陣表示法，c實現它們的方式，並尋找矢量模式匹配算法，但有很多事情要記住，需要一些指針才能從其中至少一個開始 – guiman 2011-06-06 23:45:50