A SUBLINEAR ALGORITHM FOR 2-DIMENSIONAL STRING-MATCHING

Authors
TARHIO J
Citation
J. Tarhio, A SUBLINEAR ALGORITHM FOR 2-DIMENSIONAL STRING-MATCHING, Pattern recognition letters, 17(8), 1996, pp. 833-838
Citations number
12
Categorie Soggetti
Computer Sciences, Special Topics","Computer Science Artificial Intelligence
Journal title
Pattern recognition letters → ACNP
ISSN journal
01678655
Volume
17
Issue
8
Year of publication
1996
Pages
833 - 838
Database
ISI
SICI code
0167-8655(1996)17:8<833:ASAF2S>2.0.ZU;2-R
Abstract
A simple algorithm based on the Boyer-Moore idea is presented for two- dimensional string matching. The algorithm examines a strip of columns at a time, and the shift of the pattern is based on a string of sever al characters on a row. The expected running time is shown to be subli near for random texts and patterns. The algorithm is easy to implement , and it works well in practice.