Alphabet independent approach to two-dimensional pattern matching

Amihood Amir; Gary Benson; Martin Farach

doi:10.1137/S0097539792226321

Alphabet independent approach to two-dimensional pattern matching

Amihood Amir, Gary Benson, Martin Farach

Research output: Contribution to journal › Article › peer-review

Abstract

The authors show an algorithm for two-dimensional matching with an O(n²log 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 language	English (US)
Pages (from-to)	313-323
Number of pages	11
Journal	SIAM Journal on Computing
Volume	23
Issue number	2
DOIs	https://doi.org/10.1137/S0097539792226321
State	Published - 1994

ASJC Scopus subject areas

General Computer Science
General Mathematics

Access to Document

10.1137/S0097539792226321

Cite this

@article{bd31baebfd85404991263fa5229871c1,

title = "Alphabet independent approach to two-dimensional pattern matching",

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.",

author = "Amihood Amir and Gary Benson and Martin Farach",

year = "1994",

doi = "10.1137/S0097539792226321",

language = "English (US)",

volume = "23",

pages = "313--323",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - Alphabet independent approach to two-dimensional pattern matching

AU - Amir, Amihood

AU - Benson, Gary

AU - Farach, Martin

PY - 1994

Y1 - 1994

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0028407990&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028407990&partnerID=8YFLogxK

U2 - 10.1137/S0097539792226321

DO - 10.1137/S0097539792226321

M3 - Article

AN - SCOPUS:0028407990

SN - 0097-5397

VL - 23

SP - 313

EP - 323

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 2

ER -

Alphabet independent approach to two-dimensional pattern matching

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this