A Boyer-Moore Approach for Two-Dimensional Matching
Jorma Tarhio
EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-93-784
December 1993
http://www.eecs.berkeley.edu/Pubs/TechRpts/1993/CSD-93-784.pdf
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.
BibTeX citation:
@techreport{Tarhio:CSD-93-784,
Author = {Tarhio, Jorma},
Title = {A Boyer-Moore Approach for Two-Dimensional Matching},
Institution = {EECS Department, University of California, Berkeley},
Year = {1993},
Month = {Dec},
URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1993/6322.html},
Number = {UCB/CSD-93-784}
}
EndNote citation:
%0 Report %A Tarhio, Jorma %T A Boyer-Moore Approach for Two-Dimensional Matching %I EECS Department, University of California, Berkeley %D 1993 %@ UCB/CSD-93-784 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1993/6322.html %F Tarhio:CSD-93-784