string - 有没有关于如何实现二维 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 算法——有效地在二维网格中搜索模式。

我不确定这是否是您正在寻找的，但希望它有所帮助！