定義 ：後綴數組（suffix array）是將字符串的所有後綴進行排序放入數組中。後綴樹（suffix tree）則是所有後綴形成的字典樹（trie）的壹種壓縮表示。後綴數組相對後綴樹來說，使用的存儲空間更小（只用保存原始字符串和壹個長度相同的整數數組）。
後綴樹在字符串的很多算法（例如查找，匹配，最長公***子串等）中有廣泛應用，是壹種非常實用的數據結構。
後綴數組的表示為: [5,3,1,0,4,2], 其中數字表示後綴首字母再整個字符串中的位置（即從0開始的下標）。
使用最“笨”的方法可以在 時間復雜度內構建後綴數組，其中 是字符串長度。思路是使用 的排序算法對後綴字符串排序，同時保持後綴起始字符下標。因為兩個字符串比較大小需要 復雜度，所以整體復雜度為 。
本文介紹壹種 的後綴數組構建算法。簡單期間，首先考慮 復雜度的算法。出發點是充分利用所有後綴字符串都是來源於壹個字符串的特點，同時借鑒radix排序思路。算法由 輪排序完成，第1輪排序只對第1個字符排序，第2輪排序對前2個字符排序，第3輪排序對前4個字符排序，第k輪排序對前 個字符排序。註意這裏有壹點很重要，如果所有後綴字符串已經按照前 字符排序，則可以使用 時間按照前 排序，原因是 兩個suffix可以在常數 （而不是 ）時間 內比較大小。 後綴數組
例 ：構建字符串banana的後綴數組
為每個suffix分配壹個序號rank，例如，對第 個字符串分配rank為 str[i]-'a' 。這樣，得到下面rank表：
根據前2個字符排序 ：
對於每個字符，同時保存和它相鄰的下壹個字符的序號（記為next rank）。特殊情況，對於最後壹個字符，它的next rank標記為-1。得到下面表：
先根據rank，再根據next rank對所有後綴字符串排序，結果如下表：
根據前4個字符排序
對前面排序結果，給所有後綴字符串逐個分配新rank。第1個suffix的rank為0；從第2個suffix開始，根據其rank和next rank 組合是否和上壹個組合相同分配rank，如果不同，rank加1，如果相同，rank不變。如下面表所示：
對每個suffix ( str[i] )，同時存儲 str[i+2] 的rank為next rank。如果 i+2>=n ，則next rank為-1，得到下表：
按照上面表中Rank和Next Rank對所有suffix排序，結果如下表：
至此，排序結束，後綴數組生成。
程序輸出:
總結
可以發現，後綴數組的構建充分利用了後綴數組的特性（相鄰suffix的rank）來快速比較兩個字符串，來降低構建復雜性，rank的計算復雜性為 。同時註意上面算法使用了標準（快速）排序，時間復雜度為 ，可以使用基數Radix排序（時間復雜度為 )來降低整個算法復雜性為 。
參考資料