Is there any document or explanation of how to implement two-dimensional ILC?

Question

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

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

For instance:

A = abcbcb bcacac dababa qasdqa 

and

 B = bcb cac aba 

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

Answer 1

There is an algorithm called the Baker-Bird algorithm, which I just recently met, which seems to be a partial generalization of KMP to two dimensions. It uses two algorithms as routines: the Aho-Corasick algorithm (which itself is a generalization of KMP) and the KMP algorithm - to efficiently search for a two-dimensional grid for a template.

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