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

我想在一个巨大的矩阵中找到一个子矩阵，所以我google找到Baker-Bird算法。2D字符串匹配：Baker-Bird算法

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

我找不到一些示例代码来学习。

所以我想问的是我可以研究一些简单的示例代码或伪代码吗？

Thx提前。

来源

2013-05-30 Liang-Yu Pan

好了，从研究的链接肯特·蒙特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）

（请注意，整个算法当然可以被翻转来首先进行排列，这是相同的。）

来源

2013-05-30 23:53:49 Patashu

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

来源

2013-05-30 23:43:34

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

回答

相关问题