UC BERKELEY
EECS technical reports
TECHNICAL REPORTS


CSD-93-784.pdf
CSD-93-784.ps
Oskicat catalog record
Conditions of Use

Archive Home Page

A Boyer-Moore Approach for Two-Dimensional Matching

Authors:
Tarhio, Jorma
Technical Report Identifier: CSD-93-784
December 14, 1993
CSD-93-784.pdf
CSD-93-784.ps

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.