????在字符串的處理當(dāng)中，后綴樹和后綴數(shù)組都是非常有力的工具。其實(shí)后綴數(shù)組是后綴樹的一個(gè)精巧的替代品，它比后綴樹容易實(shí)現(xiàn)，能夠?qū)崿F(xiàn)后綴樹的很多功能而時(shí)間復(fù)雜度也不太遜色，并且，它比后綴數(shù)組所占用的空間小很多。可以說，在信息學(xué)競(jìng)賽中后綴數(shù)組比后綴樹要更為實(shí)用。

?1. 后綴數(shù)組的相關(guān)概念

????后綴： 后綴是指從某個(gè)位置 i 開始到整個(gè)串末尾結(jié)束的一個(gè)特殊子串。字符串 s 的從第 i 個(gè)字符開始的后綴表示為Suffix(i) ,也可以稱為下標(biāo)為 i 的后綴。

?????例如：字符串 s = "aabaaaab" ，其后綴為， Suffix(0) = "aabaaaab", Suffix(1) = "abaaaab"

????后綴數(shù)組（Suffix Array）：后綴數(shù)組是指將所有后綴從小到大進(jìn)行排序后，把排好序的后綴的下標(biāo) i 放入數(shù)組中，該數(shù)組稱為后綴數(shù)組 SA。后綴數(shù)組記錄的是下標(biāo)。

????排名數(shù)組：是指下標(biāo)為 i 的后綴排序后的名次。例如上面的例子，排序后的下標(biāo)和名次，如圖所示。rank[i] = num, 下標(biāo)為 i 的后綴排序后的名次為 num。

????排名數(shù)組和后綴數(shù)組是可逆的，可以來回轉(zhuǎn)換。

2. 后綴數(shù)組的構(gòu)建思路

????因?yàn)楸对鏊惴?，每次比較的字符數(shù)翻倍，因此長(zhǎng)度為 n 的字符串，最多需要 O(log n)排序，除了第一次排序外，后面的都是對(duì)二元組進(jìn)行排序，如果采用快速排序，每次需要 O(log n) ，總時(shí)間復(fù)雜度為 O(nlog^2 n),而使用基數(shù)排序，每次時(shí)間復(fù)雜度為O(n),總時(shí)間復(fù)雜度為O(n log n)。因此采用基數(shù)排序?qū)崿F(xiàn)。

3. 后綴數(shù)組的應(yīng)用

1）最長(zhǎng)重復(fù)子串

2）不同子串的個(gè)數(shù)