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

Question

我想在一个巨大的矩阵中找到一个子矩阵，所以我谷歌并找到了 Baker-Bird 算法。

但是，不幸的是我不太了解它，关于它的教程很少见。

我找不到一些示例代码来研究。

那么我想问的是有没有一些简单的示例代码或者伪代码可以学习呢？

提前谢谢。

Answer 1

好的，通过研究 Kent Munthe Caspersen 给出的链接（http://www.stringology.org/papers/Zdarek-PhD_thesis-2010.pdf第 30 页），我了解了 Baker-Bird 算法的工作原理。

对于要出现在矩阵中的子矩阵，它的列必须全部单独匹配。您可以向下扫描每一列以查找匹配项，然后扫描此后处理矩阵以查找指示在同一点连续匹配的列的行。

假设我们正在寻找格式的子矩阵

a c a
b b a
c a b

我们在每一列中搜索列匹配“abc”、“cba”或“aab”，并在一个新矩阵中标记相应单元格中这些完整匹配的结尾 - 例如用 A、B 或 C。（算法是什么在论文中所做的是构建一个状态机，该状态机根据旧状态编号以及接下来出现的字母转换到新状态，然后查找表明我们刚刚匹配了一个列的状态，这更复杂但更有效，因为它只必须扫描每列一次，而不是每个我们感兴趣的不同列匹配一次）

完成此操作后，我们会沿着每一行扫描以查找指示匹配的连续列的连续值 - 在这种情况下，我们正在矩阵行中查找字符串 'ABC'。如果我们找到它，这里有一个子数组匹配。

Speedups are attained from using the state machine approach described above, and also from choice of string searching algorithm ( there are many with different time complexities: ( of which there are numerous: http://en.wikipedia.org/wiki/String_searching_algorithm )

---

(Note that the entire algorithm can, of course, be flipped to do rows first than columns, it's identical.)

Answer 2

这篇博士论文 p.31-33 中的例子怎么样：http: //www.stringology.org/papers/Zdarek-PhD_thesis-2010.pdf