Optimal parallel suffix tree construction

Hariharan, Ramesh (1997) Optimal parallel suffix tree construction Journal of Computer and System Sciences, 55 (1). pp. 44-69. ISSN 0022-0000

Full text not available from this repository.

Official URL: http://www.sciencedirect.com/science/article/pii/S...

Related URL: http://dx.doi.org/10.1006/jcss.1997.1496


An O (m)-work, O (m)-space, O (log4 m)-time CREW-PRAM algorithm for constructing the suffix tree of a string s of length m drawn from any fixed alphabet set is obtained. This is the first known work and space optimal parallel algorithm for this problem. It can be generalized to a string s drawn from any general alphabet set to perform in O (log4 m) time and O (m log |Σ|) work and space, after the characters in s have been sorted alphabetically, where |Σ| is the number of distinct characters in s. In this case too, the algorithm is work-optimal.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
ID Code:102267
Deposited On:09 Mar 2018 11:23
Last Modified:09 Mar 2018 11:23

Repository Staff Only: item control page