有没有关于如何实现二维 KMP 的论文或解释？

Question

我尝试使用 Aho-Corasick 和一维 KMP 的组合来解决二维搜索的问题，但是，我仍然需要更快的东西。

详细地说，我有一个大小为 n1*n2 的字符矩阵 A，我希望找到大小为 m1*m2 的较小矩阵 B 的所有出现，我希望它在 O(n1*n2+m1*m2) 中，如果可能的。

例如：

A = a b c b c b
    b c a c a c
    d a b a b a
    q a s d q a

和

B = b c b
    c a c
    a b a

算法应该返回比如匹配项左上角的索引，在这种情况下应该返回 (0,1) 和 (0,3)。请注意，这些事件可能会重叠。

Answer 1

我最近遇到了一种名为Baker-Bird 算法的算法，它似乎是 KMP 到二维的部分推广。它使用两种算法作为子例程 - Aho-Corasick 算法（其本身是 KMP 的推广）和 KMP 算法 - 来有效地搜索二维网格中的模式。

我不确定这是否是您要找的，但希望它有帮助！