Parallel Log-time Construction of Suffix Trees
Alberto Apostolico, Costas S. Iliopoulos · Purdue e-Pubs (Purdue University System) · 1986
Many string matching applications are based on suffix trees. Linear time sequential algorithms are available for constructing such trees. A CReW Parnllel RAM algorithm is presented here which takes 0 (logn) time with n processors, n being the length of the input string. The algorithm requires ern2) space, but only 0 (n iogn) cells need to be initialized.