| Abstract (2007) | |||||||||||||||
Abstract | |||||||||||||||
| 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(log 4 m) time and O(m log j\Sigmaj) work and space, after the characters in s have been sorted alphabetically, where j\Sigmaj is the number of distinct characters in s. In this case too, the algorithm is work-optimal. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||