Faster suffix tree construction with missing suffix links

Richard Cole; Ramesh Hariharan

doi:10.1145/335305.335352

Faster suffix tree construction with missing suffix links

Richard Cole, Ramesh Hariharan

Computer Science

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

Abstract

We consider suffix tree construction for situations with missing suffix links. Two examples of such situations are suffix trees for parameterized strings and suffix trees for 2D arrays. These trees also have the property that the node degrees may be large. We add a new back-propagation component to McCreight's algorithm and also give a high probability perfect hashing scheme to cope with large degrees. We show that these two features enable construction of suffix trees for general situations with missing suffix links in O(n) time, with high probability. This gives the first randomized linear time algorithm for constructing suffix trees for parameterized strings.

Original language	English (US)
Title of host publication	Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000
Pages	407-415
Number of pages	9
DOIs	https://doi.org/10.1145/335305.335352
State	Published - 2000
Event	32nd Annual ACM Symposium on Theory of Computing, STOC 2000 - Portland, OR, United States Duration: May 21 2000 → May 23 2000

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)	0737-8017

Conference

Conference	32nd Annual ACM Symposium on Theory of Computing, STOC 2000
Country/Territory	United States
City	Portland, OR
Period	5/21/00 → 5/23/00

ASJC Scopus subject areas

Software

Access to Document

10.1145/335305.335352

Cite this

Cole, R & Hariharan, R 2000, Faster suffix tree construction with missing suffix links. in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000. Proceedings of the Annual ACM Symposium on Theory of Computing, pp. 407-415, 32nd Annual ACM Symposium on Theory of Computing, STOC 2000, Portland, OR, United States, 5/21/00. https://doi.org/10.1145/335305.335352

@inproceedings{5d40d8256bc04c2f815f4cccf244db56,

title = "Faster suffix tree construction with missing suffix links",

abstract = "We consider suffix tree construction for situations with missing suffix links. Two examples of such situations are suffix trees for parameterized strings and suffix trees for 2D arrays. These trees also have the property that the node degrees may be large. We add a new back-propagation component to McCreight's algorithm and also give a high probability perfect hashing scheme to cope with large degrees. We show that these two features enable construction of suffix trees for general situations with missing suffix links in O(n) time, with high probability. This gives the first randomized linear time algorithm for constructing suffix trees for parameterized strings.",

author = "Richard Cole and Ramesh Hariharan",

year = "2000",

doi = "10.1145/335305.335352",

language = "English (US)",

isbn = "1581131844",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

pages = "407--415",

booktitle = "Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000",

note = "32nd Annual ACM Symposium on Theory of Computing, STOC 2000 ; Conference date: 21-05-2000 Through 23-05-2000",

}

TY - GEN

T1 - Faster suffix tree construction with missing suffix links

AU - Cole, Richard

AU - Hariharan, Ramesh

PY - 2000

Y1 - 2000

N2 - We consider suffix tree construction for situations with missing suffix links. Two examples of such situations are suffix trees for parameterized strings and suffix trees for 2D arrays. These trees also have the property that the node degrees may be large. We add a new back-propagation component to McCreight's algorithm and also give a high probability perfect hashing scheme to cope with large degrees. We show that these two features enable construction of suffix trees for general situations with missing suffix links in O(n) time, with high probability. This gives the first randomized linear time algorithm for constructing suffix trees for parameterized strings.

AB - We consider suffix tree construction for situations with missing suffix links. Two examples of such situations are suffix trees for parameterized strings and suffix trees for 2D arrays. These trees also have the property that the node degrees may be large. We add a new back-propagation component to McCreight's algorithm and also give a high probability perfect hashing scheme to cope with large degrees. We show that these two features enable construction of suffix trees for general situations with missing suffix links in O(n) time, with high probability. This gives the first randomized linear time algorithm for constructing suffix trees for parameterized strings.

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

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

U2 - 10.1145/335305.335352

DO - 10.1145/335305.335352

M3 - Conference contribution

AN - SCOPUS:0033690736

SN - 1581131844

SN - 9781581131840

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 407

EP - 415

BT - Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000

T2 - 32nd Annual ACM Symposium on Theory of Computing, STOC 2000

Y2 - 21 May 2000 through 23 May 2000

ER -

Faster suffix tree construction with missing suffix links

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this