我尝试使用 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)。请注意,事件可能重叠。