An incomplex algorithm for fast suffix array construction

Schürmann K-B, Stoye J. An incomplex algorithm for fast suffix array construction. SOFTWARE-PRACTICE & EXPERIENCE. 2007;37(3):309-329.The suffix array of a string is a permutation of all starting positions of the string's suffixes that are lexicographically sorted. We present a practical algorithm for suffix array construction that consists of two easy-to-implement components. First it sorts the suffixes with respect to a fixed length prefix; then it refines each bucket of suffixes sharing the same prefix using the order of already sorted suffixes. Other suffix array construction algorithms follow more complex strategies. Moreover, we achieve a very fast construction for common strings as well as for worst case strings by enhancing our algorithm with further techniques. Copyright (C) 2006 John Wiley & Sons, Ltd