Linear Time Construction of Suffix Arrays

A linear time algorithm to sort all the suffixes of a string over a large alphabet of integers, which improves upon the best known direct algorithm for suffix sorting, which takes O(n log n) time.