Alphabet independent approach to two-dimensional pattern matching

Amihood Amir, Gary Benson, Martin Farach

Research output: Contribution to journalArticlepeer-review

64 Scopus citations

Abstract

The authors show an algorithm for two-dimensional matching with an O(n2log m ) text-scanning phase. Furthermore, the text scan requires no special assumptions about the alphabet, i.e. it runs on the same model as the standard linear-time string-matching algorithm. The pattern preprocessing requires an ordered alphabet and runs with the same alphabet dependency as the previously known algorithms.

Original languageEnglish
Pages (from-to)313-323
Number of pages11
JournalSIAM Journal on Computing
Volume23
Issue number2
DOIs
StatePublished - 1994
Externally publishedYes

Fingerprint

Dive into the research topics of 'Alphabet independent approach to two-dimensional pattern matching'. Together they form a unique fingerprint.

Cite this