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