Optimal Parallel Suffix Tree Construction

AbstractAnO(m)-work,O(m)-space,O(log4m)-time CREW-PRAM algorithm for constructing the suffix tree of a stringsof lengthmdrawn 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 inO(log4m) time andO(mlog|Σ|) work and space, after the characters inshave been sorted alphabetically, where |Σ| is the number of distinct characters ins. In this case too, the algorithm is work-optimal