SA-IS for Constructing Suffix Array

http://panthema.net/2012/1119-eSAIS-Inducing-Suffix-and-LCP-Arrays-in-External-Memory/alenex13esais-slides.pdf

http://web.iiit.ac.in/~abhishek_shukla/suffix/SA_implementations.pdf

http://www.bgjackson.net/bcb597/supplement/StringApplications.pdf

http://www.cs.ucf.edu/~shzhang/Combio/suffix.pdf

BWT vs Suffix Array

“Suffix sorting algorithms can be used to compute the Burrows–Wheeler transform (BWT). The BWT requires sorting of all cyclic permutations of a string. If this string ends in a special end-of-string character that is lexicographically smaller than all other character (i.e., $), then the order of the sorted rotated BWT matrix corresponds to the order of suffixes in a suffix array. The BWT can therefore be computed in linear time by first constructing a suffix array of the text and then deducing the BWT string: BWT[i] = S[A[i]-1].”

http://en.wikipedia.org/wiki/Suffix_array