A Boyer-Moore Approach for Two-Dimensional Matching

Jorma Tarhio

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-93-784

, 1993

http://www2.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},
    Year= {1993},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/6322.html},
    Number= {UCB/CSD-93-784},
    Abstract= {A simple sublinear algorithm is presented for two-dimensional string matching, where occurrences of a pattern of <i>m</i> x <i>m</i> characters are searched for in a text of <i>n</i> x <i>n</i> characters in an alphabet of <i>c</i> characters. The algorithm is based on the Boyer-Moore idea and it examines a strip of <i>r</i> columns at a time, <i>m</i>/2 <= <i>r</i> <= <i>m</i>. The shift of the pattern is based on a string of <i>d</i> characters, <i>d</i> = [log_c(<i>rm</i>)].  The expected running time of the algorithm is shown to be <i>O</i>(<i>n</i>^2 [log_c<i>m</i>^2] / <i>m</i>^2 + <i>cm</i>^2) for random texts and patterns. The algorithm is easy to implement, and results of experiments are reported to show its practical efficiency.},
}

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://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/6322.html
%F Tarhio:CSD-93-784