[ Suffix Array SA-IS Algorithm ] 後綴數組線性SA-IS算法

SA-IS是我目前看過最快的線性後綴數組演算法，但是做為競賽用途而進行簡化後他的效率在某些硬體上會比DC3慢，不過記憶體使用量是DC3的1/3~1/2倍，而最短的實現code也比DC3短很多，因此我認為這是十分優秀的算法

因為某些SA-IS的實作方式會利用傳入的陣列s的空間進行計算，因此傳入的陣列s必須是int範圍，而傳入的字串的尾端字元必須是最小的而且在之前完全沒有出現過，因此必須給字串先做以下處理:

假設要傳入字串 mississippi
先在尾端加入字元'#': mississippi#
算法結束後陣列sa為:11 10 7 4 1 0 9 8 6 3 5 2
將第一個數字11去除後剩下的數字即為字串mississippi的後綴數組:
10 7 4 1 0 9 8 6 3 5 2
關於SA-IS算法的論文請看這裡:
Two Efficient Algorithms for Linear Time Suffix Array Construction

關於SA-IS算法的教學(專利申請文)請看這裡:
后缀数组构造方法  CN 102081673 A

SA-IS的教學投影片:
https://www.cs.helsinki.fi/u/tpkarkka/opetus/11s/spa/lecture11.pdf

SA-IS中文教學:
https://riteme.github.io/blog/2016-6-19/sais.html

如果想對Suffix Array算法進行測試請使用這個Online Judge:
http://www.spoj.com/problems/SARRAY/

以下將會提供一些SA-IS的實做模板

1.台大黑暗code界的黑暗codebook:
其實這段code本來是被壓縮得更短，而且用到非常多的記憶體，不過經過卦長的改良後成功減少記憶體的使用並將他排版成正常人能看得懂的樣子
而這裡的MXN則是字串的最長長度(假設字元數<字串長度)

2.卦長自行實作的模板(記憶體用量少):
為了簡化實作方法及減少記憶體的使用，因此將計算後剩下的空間進行重複利用，壓縮後只需要這些記憶空間，而傳入的陣列s可以直接傳入char陣列，因此對使用者來說是非常方便的一份code
這裡的MXN則是字串的最長長度(假設字元數<字串長度)

3.論文提供的實作code:
這是其中一個比DC3快的code，而且記憶體使用量是最少的，但是長度很長就是了，不適合在比賽時使用

4.超快記憶體使用超少的模板庫code:
https://gist.github.com/jacky860226/1d33adad858eef71bfe18120d8d69e6d#file-sa-is-very-fast-cpp
因為長度太長所以就直接貼上網址了，沒有人會在比賽時寫這種東西