Optimal parallel suffix tree construction

An O(m)-work, O(m)-space, O(log(4) 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 \Sigma\) work and space, after the characters in s have been sorted alphabetically, where \Sigma\ is the number of distinct characters in s. In this case too, the algorithm is work-optimal. (C) 1997 Academic Press.