Optimal Parallel Suffix Tree Construction

摘要

AnO(m)-work,O(m)-space,O(log4 m)-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(log4 m) time andO(m log |Σ|) 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.