A Boyer-Moore Approach for Two-Dimensional Matching
Abstract: A simple sublinear algorithm is presented for two-dimensional string matching, where occurrences of a pattern of m x m characters are searched for in a text of n x n characters in an alphabet of c characters. The algorithm is based on the Boyer-Moore idea and it examines a strip of r columns at a time, m/2 <= r <= m. The shift of the pattern is based on a string of d characters, d = [log_c(rm)]. The expected running time of the algorithm is shown to be O(n^2 [log_cm^2] / m^2 + cm^2) for random texts and patterns. The algorithm is easy to implement, and results of experiments are reported to show its practical efficiency.