Multidimensional matching and fast search in suffix trees

Richard Cole; Moshe Lewenstein

Multidimensional matching and fast search in suffix trees

Richard Cole, Moshe Lewenstein

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We show how to construct a suffix tree of a text string t in linear time, after sorting the characters in the text, so that a search for pattern p take time O(p + log t), independent of the alphabet size, thereby matching the asymptotic performance of suffix arrays. Using these suffix trees or suffix arrays we then give linear time algorithms for pattern matching in any fixed dimension.

Original language	English (US)
Title of host publication	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Editors	J Schewel
Pages	851-852
Number of pages	2
State	Published - 2003
Event	Configuralble Computing: Technology and Applications - Boston, MA, United States Duration: Nov 2 1998 → Nov 3 1998

Other

Other	Configuralble Computing: Technology and Applications
Country/Territory	United States
City	Boston, MA
Period	11/2/98 → 11/3/98

ASJC Scopus subject areas

Chemical Health and Safety
Software
Safety, Risk, Reliability and Quality
Discrete Mathematics and Combinatorics

Cite this

@inproceedings{62b01ddc2ceb47f9b6012a1b11df5071,

title = "Multidimensional matching and fast search in suffix trees",

abstract = "We show how to construct a suffix tree of a text string t in linear time, after sorting the characters in the text, so that a search for pattern p take time O(p + log t), independent of the alphabet size, thereby matching the asymptotic performance of suffix arrays. Using these suffix trees or suffix arrays we then give linear time algorithms for pattern matching in any fixed dimension.",

author = "Richard Cole and Moshe Lewenstein",

year = "2003",

language = "English (US)",

pages = "851--852",

editor = "J Schewel",

booktitle = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

note = "Configuralble Computing: Technology and Applications ; Conference date: 02-11-1998 Through 03-11-1998",

}

TY - GEN

T1 - Multidimensional matching and fast search in suffix trees

AU - Cole, Richard

AU - Lewenstein, Moshe

PY - 2003

Y1 - 2003

N2 - We show how to construct a suffix tree of a text string t in linear time, after sorting the characters in the text, so that a search for pattern p take time O(p + log t), independent of the alphabet size, thereby matching the asymptotic performance of suffix arrays. Using these suffix trees or suffix arrays we then give linear time algorithms for pattern matching in any fixed dimension.

AB - We show how to construct a suffix tree of a text string t in linear time, after sorting the characters in the text, so that a search for pattern p take time O(p + log t), independent of the alphabet size, thereby matching the asymptotic performance of suffix arrays. Using these suffix trees or suffix arrays we then give linear time algorithms for pattern matching in any fixed dimension.

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

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

M3 - Conference contribution

AN - SCOPUS:0038754053

SP - 851

EP - 852

BT - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Schewel, J

T2 - Configuralble Computing: Technology and Applications

Y2 - 2 November 1998 through 3 November 1998

ER -

Multidimensional matching and fast search in suffix trees

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this