|
|||||
|
|
Parallel construction of a suffix tree with applications |
|
| Authors: | A. Apostolico C. Iliopoulos G. M. Landau B. Schieber U. Vishkin |
| Affiliation: | 1. Department of Computer Sciences, Purdue University, 47907, West Lafayette, IN, USA 2. Department of Computer Science, School of Mathematical Sciences, Tel Aviv University, 69978, Tel Aviv, Israel 3. Department of Computer Science, Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, 10012, New York, NY, USA |
| Abstract: | Many string manipulations can be performed efficiently on suffix trees. In this paper a CRCW parallel RAM algorithm is presented that constructs the suffix tree associated with a string ofn symbols inO(logn) time withn processors. The algorithm requires Θ(n 2) space. However, the space needed can be reduced toO(n 1+?) for any 0< ? ≤1, with a corresponding slow-down proportional to 1/?. Efficient parallel procedures are also given for some string problems that can be solved with suffix trees. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |