Two-dimensional pattern matching
In computer science, two-dimensional pattern matching is the problem of locating occurrences of a two-dimensional matrix of characters in a bigger two-dimensional matrix.
The naïve solution
Assume given a pattern and a text, where.The simplest approach is to compare P against every sub-array of size in T. This algorithm has
a worst-case time of. It is usually assume that, whence this can be written
as.
An automaton-based solution
We shall illustrate a more efficient solution by means of an example. Suppose we have the following pattern and textabaab
aba baaab
P = bab T = abaab
aba babab
ababa
We first construct a Aho-Corasick automaton to search a linear text for occurrences of the columns
of P. As a biproduct we obtain an identifier for every column, so that two identical columns get the same identifier: in our example, say the first columns are idntified by 0, and the middle column by 1.
Next, we run the automaton on the columns of T, obtaining an indication whenever one of the columns of P appears in T: in our example this will be a 3×5 matrix C as follow :
abaab
aba baaab
P = bab T = abaaa C = 01---
aba babab 10--1
ababa 010-0
We now use the Knuth-Morris-Pratt Algorithm to search the rows of C for a pattern identical to P, i.e., 010. When we find one, we have idnetified an occurrence of P in T. Note that it is not necessary to keep all of C, or all of T, in memory; T can be read row by row, and from C one only needs to keep one row in memory---along with a row of states of the Aho-Corasick and the KMP automata.
The running time of this algorithm is if one ignores the dependence on the size of the alphabet, which exists in the Aho-Corasick algorithm. Taking this into account, the complexity is where k is the size of the alphabet.