数据结构之后缀数组
后綴數組是一種解決字符串問題的有力工具。相比于后綴樹，它更易于實現且占用內存更少。在實際應用中，后綴數組經常用于解決字符串有關的復雜問題。
本文大部分內容摘自參考資料[1][2]。
2. 后綴數組
2.1?? 幾個概念
（1）后綴數組SA 是一個一維數組，它保存1..n 的某個排列SA[1]，SA[2]，……，SA[n]，并且保證Suffix(SA[i]) < Suffix(SA[i+1])，1≤i<n。也就是將S 的n 個后綴從小到大進行排序之后把排好序的后綴的開頭位置順次放入SA 中。其中，suffix(i)表示字符串s[i,i+1…n-1]，即字符串s起始于第i個字符的后綴。
（2）名次數組Rank[i]保存的是Suffix(i)在所有后綴中從小到大排列的“名次”。
簡單的說，后綴數組是“排第幾的是誰？”，名次數組是“你排第幾？”。容易看出，后綴數組和名次數組為互逆運算。
（3）height 數組：定義height[i]=suffix(SA[i-1])和suffix(SA[i])的最長公共前綴，也就是排名相鄰的兩個后綴的最長公共前綴。
（4） h[i]=height[rank[i]]，也就是suffix(i)和在它前一名的后綴的最長公共前綴。
（5）LCP(i,j)：對正整數i,j 定義LCP(i,j)=lcp(Suffix(SA[i]),Suffix(SA[j])，其中i,j 均為1 至n 的整數。LCP(i,j)也就是后綴數組中第i 個和第j 個后綴的最長公共前綴的長度。其中，函數lcp(u,v)=max{i|u=v}，也就是從頭開始順次比較u 和v 的對應字符，對應字符持續相等的最大位置，稱為這兩個字符串的最長公共前綴。
2.2?? 幾個性質
（1）LCP(i,j)=min{height[k]|i+1≤k≤j}，也就是說，計算LCP(i,j)等同于詢問一維數組height 中下標在i+1 到j 范圍內的所有元素的最小值。
證明略。
（2）對于i>1 且Rank[i]>1，一定有h[i]≥h[i-1]-1。
證明：設suffix(k)是排在suffix(i-1)前一名的后綴，則它們的最長公共前綴是h[i-1]。那么suffix(k+1)將排在suffix(i)的前面（這里要求h[i-1]>1，如果h[i-1]≤1，原式顯然成立）并且suffix(k+1)和suffix(i)的最長公共前綴是h[i-1]-1，所以suffix(i)和在它前一名的后綴的最長公共前綴至少是h[i-1]-1。按照h[1],h[2],……,h[n]的順序計算,并利用h 數組的性質，時間復雜度可以降為O(n)。
3. 后綴數組實現
本節給出高效計算SA，Rank，height和h的算法
（1） 計算名次數組Rank與后綴數組SA
采用倍增算法，先求出名次Rank，然后在O(n)時間內求得后綴數組SA。用倍增的方法對每個字符開始的長度為2^k 的子字符串進行排序，求出排名，即rank 值。k 從0 開始，每次加1，當2k 大于n 以后，每個字符開始的長度為2^k 的子字符串便相當于所有的后綴。并且這些子字符串都一定已經比較出大小，即rank 值中沒有相同的值，那么此時的rank 值就是最后的結果。每一次排序都利用上次長度為2^(k-1) 的字符串的rank 值，那么長度為2^k 的字符串就可以用兩個長度為2^(k-1) 的字符串的排名作為關鍵字表示，然后進行基數排序，便得出了長度為2k 的字符串的rank 值。以字符串“aabaaaab”為例，整個過程如下圖所示。其中x、y 是表示長度為2k 的字符串的兩個關鍵字。
（2） 計算數組h
可以令i從1 循環到n按照如下方法依次算出h[i]：
若 Rank[i]=1，則h[i]=0。字符比較次數為0。
若 i=1 或者h[i-1]≤1，則直接將Suffix(i)和Suffix(Rank[i]-1)從第一個字符開始依次比較直到有字符不相同，由此計算出h[i]。字符比較次數為h[i]+1，不超過h[i]-h[i-1]+2。
否則，說明i>1，Rank[i]>1，h[i-1]>1，根據性質2，Suffix(i)和Suffix(Rank[i]-1)至少有前h[i-1]-1 個字符是相同的，于是字符比較可以從h[i-1]開始，直到某個字符不相同，由此計算出h[i]。字符比較次數為h[i]-h[i-1]+2。
可求得最后算法復雜度為O(n)。
4. 后綴數組應用
4.1 單個字符串相關問題
（1） 可重疊最長重復子串。給定一個字符串，求最長重復子串，這兩個子串可以重疊。
『解析』只需要求height 數組里的最大值即可。
（2） 不可重疊最長重復子串。給定一個字符串，求最長重復子串，這兩個子串不能重疊。
『解析』先二分答案，把題目變成判定性問題：判斷是否存在兩個長度為k 的子串是相同的，且不重疊。解決這個問題的關鍵還是利用height 數組。把排序后的后綴分成若干組，其中每組的后綴之間的height 值都不小于k。例如，字符串為“aabaaaab”，當k=2 時，后綴分成了4 組：
容易看出，有希望成為最長公共前綴不小于k 的兩個后綴一定在同一組。然后對于每組后綴，只須判斷每個后綴的sa 值的最大值和最小值之差是否不小于k。如果有一組滿足，則說明存在，否則不存在。整個做法的時間復雜度為O(nlogn)。
（3） 可重疊的k 次最長重復子串。給定一個字符串，求至少出現k 次的最長重復子串，這k 個子串可以重疊。
『解析』 先二分答案，然后將后綴分成若干組。不同的是，這里要判斷的是有沒有一個組的后綴個數不小于k。如果有，那么存在k 個相同的子串滿足條件，否則不存在。這個做法的時間復雜度為O(nlogn)。
（4） 最長回文子串。給定一個字符串，求最長回文子串。
『解析』 將整個字符串反過來寫在原字符串后面，中間用一個特殊的字符隔開。這樣就把問題變為了求這個新的字符串的某兩個后綴的最長公共前綴。
（5） 連續重復子串。給定一個字符串L，已知這個字符串是由某個字符串S 重復R 次而得到的，求R 的最大值。
『解析』窮舉字符串S 的長度k，然后判斷是否滿足。判斷的時候，先看字符串L 的長度能否被k 整除，再看suffix(1)和suffix(k+1)的最長公共前綴是否等于n-k。在詢問最長公共前綴的時候，suffix(1)是固定的，所以RMQ問題沒有必要做所有的預處理， 只需求出height 數組中的每一個數到height[rank[1]]之間的最小值即可。整個做法的時間復雜度為O(n)。
（6） 重復次數最多的連續重復子串。給定一個字符串，求重復次數最多的連續重復子串。
『解析』先窮舉長度L，然后求長度為L 的子串最多能連續出現幾次。首先連續出現1 次是肯定可以的，所以這里只考慮至少2 次的情況。假設在原字符串中連續出現2 次，記這個子字符串為S，那么S 肯定包括了字符r[0], r[L], r[L*2],r[L*3], ……中的某相鄰的兩個。所以只須看字符r[L*i]和r[L*(i+1)]往前和往后各能匹配到多遠，記這個總長度為K，那么這里連續出現了K/L+1 次。最后看最大值是多少。
窮舉長度L 的時間是n，每次計算的時間是n/L。所以整個做法的時間復雜度是O(n/1+n/2+n/3+……+n/n)=O(nlogn)。
4.2 兩個字符串相關問題
（1） 最長公共子串。給定兩個字符串A 和B，求最長公共子串。
『解析』先將第二個字符串寫在第一個字符串后面，中間用一個沒有出現過的字符隔開，再求這個新的字符串的后綴數組。當suffix(sa[i-1]) 和suffix(sa[i])不是同一個字符串中的兩個后綴時，max{height[i]}才是滿足條件
（2） 長度不小于k 的公共子串的個數。給定兩個字符串A 和B，求長度不小于k 的公共子串的個數（可以相同）。
『解析』基本思路是計算A 的所有后綴和B 的所有后綴之間的最長公共前綴的長度，把最長公共前綴長度不小于k 的部分全部加起來。先將兩個字符串連起來，中間用一個沒有出現過的字符隔開。按height 值分組后，接下來的工作便是快速的統計每組中后綴之間的最長公共前綴之和。掃描一遍，每遇到一個B 的后綴就統計與前面的A 的后綴能產生多少個長度不小于k 的公共子串，這里A 的后綴需要用一個單調的棧來高效的維護。然后對A 也這樣做一次。
4.3 多個字符串相關問題
（1） 不小于k 個字符串中的最長子串。給定n 個字符串，求出現在不小于k 個字符串中的最長子串。
『解析』將n 個字符串連起來，中間用不相同的且沒有出現在字符串中的字符隔開，求后綴數組。然后二分答案：將后綴分成若干組，判斷每組的后綴是否出現在不小于k 個的原串中。這個做法的時間復雜度為O(nlogn)。
（2） 每個字符串至少出現兩次且不重疊的最長子串。給定n 個字符串，求在每個字符串中至少出現兩次且不重疊的最長子串。
『解析』做法和上題大同小異，也是先將n 個字符串連起來，中間用不相同的且沒有出現在字符串中的字符隔開，求后綴數組。然后二分答案，再將后綴分組。判斷的時候，要看是否有一組后綴在每個原來的字符串中至少出現兩次，并且在每個原來的字符串中，后綴的起始位置的最大值與最小值之差是否不小于當前答案（判斷能否做到不重疊，如果題目中沒有不重疊的要求，那么不用做此判斷）。這個做法的時間復雜度為O(nlogn)。
（3） 出現或反轉后出現在每個字符串中的最長子串。給定n 個字符串，求出現或反轉后出現在每個字符串中的最長子串。
『解析』這題不同的地方在于要判斷是否在反轉后的字符串中出現。其實這并沒有加大題目的難度。只需要先將每個字符串都反過來寫一遍，中間用一個互不相同的且沒有出現在字符串中的字符隔開，再將n 個字符串全部連起來，中間也是用一個互不相同的且沒有出現在字符串中的字符隔開，求后綴數組。然后二分答案，再將后綴分組。判斷的時候，要看是否有一組后綴在每個原來的字符串或反轉后的字符串中出現。這個做法的時間復雜度為O(nlogn)。
5. 總結
后綴數組實際上可以看作后綴樹的所有葉結點按照從左到右的次序排列放入數組中形成的，所以后綴數組的用途不可能超出后綴樹的范圍。甚至可以說，如果不配合LCP，后綴數組的應用范圍是很狹窄的。但是LCP 函數配合下的后綴數組就非常強大，可以完成大多數后綴樹所能完成的任務，因為LCP 函數實際上給出了任意兩個葉子結點的最近公共祖先，這方面的內容大家可以自行研究。
6. 參考資料
（1） 許智磊，IOI2004 國家集訓隊論文《后綴數組》
（2） 羅穗騫，IOI2004 國家集訓隊論文《后綴數組—處理字符串的有力工具》
---------------------------------------------------------------------------------------------- 更多關于數據結構和算法的介紹，請查看：數據結構與算法匯總 ----------------------------------------------------------------------------------------------原創文章，轉載請注明：?轉載自董的博客
本文鏈接地址:?http://dongxicheng.org/structure/suffix-array/
總結
- 上一篇： 数据结构之Treap
- 下一篇： 数据结构之伸展树