Faster suffix tree construction with missing suffix links

Cole, Richard ; Hariharan, Ramesh (2003) Faster suffix tree construction with missing suffix links SIAM Journal on Computing, 33 (1). pp. 26-42. ISSN 0097-5397

Full text not available from this repository.

Official URL:

Related URL:


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 two-dimensional 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 hashing scheme for 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.

Item Type:Article
Source:Copyright of this article belongs to Society for Industrial and Applied Mathematics.
ID Code:102266
Deposited On:09 Mar 2018 11:23
Last Modified:09 Mar 2018 11:23

Repository Staff Only: item control page