有没有纸或如何实现二维KMP的解释？ [英] is there any paper or an explanation on how to implement a two dimensional KMP?

问题描述

我试图用阿霍Corasick和一维KMP的结合，解决了二维搜索的问题，但是，我还是需要一些速度更快。

I tried to solve the problem of two dimensional search using a combination of Aho-Corasick and a single dimensional KMP, however, I still need something faster.

要详细说明，我有尺寸的字符N1 * N2的矩阵A，我希望找到的大小M1 *平方米的小矩阵B的所有出现，我想这是在O（N1 * N2 + M1 *平方米）如果可能的话。

To elaborate, I have a matrix A of characters of size n1*n2 and I wish to find all occurrences of a smaller matrix B of size m1*m2 and I want that to be in O(n1*n2+m1*m2) if possible.

例如：

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）的左上角。注意到可能发生重叠。

the algorithm should return the indexes of say, the upper left corner of the match, which in this case should return (0,1) and (0,3). notice that the occurrences may overlap.

推荐答案

有叫的贝克 - 鸟算法，似乎是KMP的部分推广到两个方面，我刚刚遇到过。它使用两种算法作为子程序 - 在阿霍Corasick算法（这本身是KMP的一般化）和KMP算法 - 有效地搜索一个二维网格的图案

There is an algorithm called the Baker-Bird algorithm that I just recently encountered that appears to be a partial generalization of KMP to two dimensions. It uses two algorithms as subroutines - the Aho-Corasick algorithm (which itself is a generalization of KMP), and the KMP algorithm - to efficiently search a two-dimensional grid for a pattern.

我不知道如果这是你在找什么，但我希望它能帮助！

I'm not sure if this is what you're looking for, but hopefully it helps!

这篇关于有没有纸或如何实现二维KMP的解释？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！