2D字符串匹配：Baker-Bird算法

Question

我想在一個巨大的矩陣中找到一個子矩陣，所以我google找到Baker-Bird算法。

但是，不幸的是我不能理解它，關於它的教程很少。

我找不到一些示例代碼來學習。

所以我想問的是我可以研究一些簡單的示例代碼或僞代碼嗎？

Thx提前。

Answer 1

好了，從研究的鏈接肯特·蒙特Caspersen給（http://www.stringology.org/papers/Zdarek-PhD_thesis-2010.pdf第30頁），我明白是怎麼貝克鳥算法工程。

要使子矩陣出現在矩陣中，其列必須全部匹配。您可以掃描每列查找匹配項，然後掃描此後處理矩陣的行，以指示在同一地點連續匹配的列。

說，我們正在尋找的格式的子矩陣

a c a 
b b a 
c a b 

我們爲列匹配「ABC」「CBA」或「AAB」，並在新的矩陣紀念那些末端上的每個列向下搜索在相應的單元格中完成匹配 - 例如與A，B或C相關（本文算法的作用是構造一個狀態機，該狀態機根據舊狀態編號轉換爲新狀態，然後顯示下一個字母，然後顯示對於那些表明我們只匹配一列的狀態，這個列更復雜但更有效，因爲它只需要掃描每一列而不是每個列匹配一次，我們感興趣）

一旦我們完成了這一步，我們沿着每一行進行掃描，尋找表示連續列匹配的連續值 - 在這種情況下，我們在矩陣行中查找字符串「ABC」。如果我們找到它，這裏有一個子數組匹配。

加速比從使用上述狀態機方法實現的，並且還從串搜索算法的選擇（有許多不同的時間複雜性：（其中有許多：http://en.wikipedia.org/wiki/String_searching_algorithm）

---

（請注意，整個算法當然可以被翻轉來首先進行排列，這是相同的。）

Answer 2

怎麼樣在這個博士論文p.31-33的例子： http://www.stringology.org/papers/Zdarek-PhD_thesis-2010.pdf