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
Abstract
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
