What’s the current state-of-the-art suffix array construction algorithm?
Currently, the best Suffix-Array constructor known is LibDivSufSort, by Yuta Mori : http://code.google.com/p/libdivsufsort/ It uses Induced Sorting methodology (Basically, after sorting all strings starting with “A*”, you can induce sortings of strings “BA*” “CA*” “DA*” etc.) It is praised everywhere for its efficiency and nice handling of degenerated cases. It’s also the fastest, and uses … Read more