在字符串處理當中，後綴樹和後綴數組都是非常有力的工具，其中後綴樹大家了解得比較多，關於後綴數組則很少見於國內的資料。其實後綴數組是後綴樹的壹個非常精巧的替代品，它比後綴樹容易編程實現，能夠實現後綴樹的很多功能而時間復雜度也不太遜色，並且，它比後綴樹所占用的空間小很多。可以說，在信息學競賽中後綴數組比後綴樹要更為實用。因此在本文中筆者想介紹壹下後綴數組的基本概念、構造方法，以及配合後綴數組的最長公***前綴數組的構造方法，最後結合壹些例子談談後綴數組的應用。
基本概念
首先明確壹些必要的定義：
字符集 壹個字符集∑是壹個建立了全序關系的集合，也就是說，∑中的任意兩個不同的元素α和β都可以比較大小，要麽α<β，要麽β<α（也就是α>β）。字符集∑中的元素稱為字符。
字符串 壹個字符串S是將n個字符順次排列形成的數組，n稱為S的長度，表示為len(S)。S的第i個字符表示為S。
子串 字符串S的子串S[i..j]，i≤j，表示S串中從i到j這壹段，也就是順次排列S,S[i+1],...,S[j]形成的字符串。
後綴 後綴是指從某個位置i開始到整個串末尾結束的壹個特殊子串。字符串S的從i開頭的後綴表示為Suffix(S,i)，也就是Suffix(S,i)=S[i..len(S)]。
關於字符串的大小比較，是指通常所說的“字典順序”比較，也就是對於兩個字符串u、v，令i從1開始順次比較u和v，如果相等則令i加1，否則若u<v則認為u<v，u>v則認為u>v（也就是v<u），比較結束。如果i>len(u)或者i>len(v)仍未比較出結果，那麽若len(u)<len(v)則認為u<v，若len(u)=len(v)則認為u=v，若len(u)>len(v)則u>v。
從字符串的大小比較的定義來看，S的兩個開頭位置不同的後綴u和v進行比較的結果不可能是相等，因為u=v的必要條件len(u)=len(v)在這裏不可能滿足。
下面我們約定壹個字符集∑和壹個字符串S，設len(S)=n，且S[n]='$'，也就是說S以壹個特殊字符'$'結尾，並且'$'小於∑中的任何壹個字符。除了S[n]之外，S中的其他字符都屬於∑。對於約定的字符串S，從位置i開頭的後綴直接寫成Suffix(i)，省去參數S。
後綴數組 後綴數組SA是壹個壹維數組，它保存1..n的某個排列SA[1],SA[2],...SA[n]，並且保證 Suffix(SA)<Suffix(SA[i+1]),1≤i<n。也就是將S的n個後綴從小到大進行排序之後把排好序的後綴的開頭位置順次放入SA中。
名次數組 名次數組Rank=SA-1，也就是說若SA=j，則Rank[j]=i，不難看出Rank保存的是Suffix(i)在所有後綴中從小到大排列的“名次”。
構造方法
如何構造後綴數組呢？最直接最簡單的方法當然是把S的後綴都看作壹些普通的字符串，按照壹般字符串排序的方法對它們從小到大進行排序。
不難看出，這種做法是很笨拙的，因為它沒有利用到各個後綴之間的有機聯系，所以它的效率不可能很高。即使采用字符串排序中比較高效的Multi-key Quick Sort，最壞情況的時間復雜度仍然是O(n2)的，不能滿足我們的需要。
下面介紹倍增算法(Doubling Algorithm)，它正是充分利用了各個後綴之間的聯系，將構造後綴數組的最壞時間復雜度成功降至O(nlogn)。
對壹個字符串u，我們定義u的k-前綴
定義k-前綴比較關系<k、=k和≤k：
設兩個字符串u和v，
u<kv 當且僅當 uk<vk
u=kv 當且僅當 uk=vk
u≤kv 當且僅當 uk≤vk
直觀地看這些加了壹個下標k的比較符號的意義就是對兩個字符串的前k個字符進行字典序比較，特別的壹點就是在作大於和小於的比較時如果某個字符串的長度不到k也沒有關系，只要能夠在k個字符比較結束之前得到第壹個字符串大於或者小於第二個字符串就可以了。
根據前綴比較符的性質我們可以得到以下的非常重要的性質：
性質1.1 對k≥n，Suffix(i)<kSuffix(j) 等價於 Suffix(i)<Suffix(j)。
性質1.2 Suffix(i)=2kSuffix(j)等價於
Suffix(i)=kSuffix(j) 且 Suffix(i+k)=kSuffix(j+k)。
性質1.3 Suffix(i)<2kSuffix(j) 等價於
Suffix(i)<kS(j) 或 (Suffix(i)=kSuffix(j) 且 Suffix(i+k)<kSuffix(j+k))。
這裏有壹個問題，當i+k>n或者j+k>n的時候Suffix(i+k)或Suffix(j+k)是無明確定義的表達式，但實際上不需要考慮這個問題，因為此時Suffix(i)或者Suffix(j)的長度不超過k，也就是說它們的k-前綴以'$'結尾，於是k-前綴比較的結果不可能相等，也就是說前k個字符已經能夠比出大小，後面的表達式自然可以忽略，這也就看出我們規定S以'$'結尾的特殊用處了。
定義k-後綴數組SAk保存1..n的某個排列SAk[1],SAk[2],…SAk[n]使得Suffix(SAk) ≤kSuffix(SAk[i+1]),1≤i<n。也就是說對所有的後綴在k-前綴比較關系下從小到大排序，並且把排序後的後綴的開頭位置順次放入數組SAk中。
定義k-名次數組Rankk，Rankk代表Suffix(i)在k-前綴關系下從小到大的“名次”，也就是1加上滿足Suffix(j)<kSuffix(i)的j的個數。通過SAk很容易在O(n)的時間內求出Rankk。
假設我們已經求出了SAk和Rankk，那麽我們可以很方便地求出SA2k和Rank2k，因為根據性質1.2和1.3，2k-前綴比較關系可以由常數個k-前綴比較關系組合起來等價地表達，而Rankk數組實際上給出了在常數時間內進行<k和=k比較的方法，即：
Suffix(i)<kSuffix(j) 當且僅當 Rankk<Rankk[j]
Suffix(i)=kSuffix(j) 當且僅當 Rankk=Rankk[j]
因此，比較Suffix(i)和Suffix(j)在k-前綴比較關系下的大小可以在常數時間內完成，於是對所有的後綴在≤k關系下進行排序也就和壹般的排序沒有什麽區別了，它實際上就相當於每個Suffix(i)有壹個主關鍵字Rankk和壹個次關鍵字Rankk[i+k]。如果采用快速排序之類O(nlogn)的排序，那麽從SAk和Rankk構造出SA2k的復雜度就是O(nlogn)。更聰明的方法是采用基數排序，復雜度為O(n)。
求出SA2k之後就可以在O(n)的時間內根據SA2k構造出Rank2k。因此，從SAk和Rankk推出SA2k和Rank2k可以在O(n)時間內完成。
下面只有壹個問題需要解決：如何構造出SA1和Rank1。這個問題非常簡單：因為<1，=1和≤1這些運算符實際上就是對字符串的第壹個字符進行比較，所以只要把每個後綴按照它的第壹個字符進行排序就可以求出SA1，不妨就采用快速排序，復雜度為O(nlogn)。
於是，可以在O(nlogn)的時間內求出SA1和Rank1。
求出了SA1和Rank1，我們可以在O(n)的時間內求出SA2和Rank2，同樣，我們可以再用O(n)的時間求出SA4和Rank4，這樣，我們依次求出：
SA2和Rank2，SA4和Rank4，SA8和Rank8，……直到SAm和Rankm，其中m=2k且m≥n。而根據性質1.1，SAm和SA是等價的。這樣壹***需要進行logn次O(n)的過程，因此
可以在O(nlogn)的時間內計算出後綴數組SA和名次數組Rank。
最長公***前綴
現在壹個字符串S的後綴數組SA可以在O(nlogn)的時間內計算出來。利用SA我們已經可以做很多事情，比如在O(mlogn)的時間內進行模式匹配，其中m,n分別為模式串和待匹配串的長度。但是要想更充分地發揮後綴數組的威力，我們還需要計算壹個輔助的工具——最長公***前綴（Longest Common Prefix）。
對兩個字符串u,v定義函數lcp(u,v)=max{i|u=iv}，也就是從頭開始順次比較u和v的對應字符，對應字符持續相等的最大位置，稱為這兩個字符串的最長公***前綴。
對正整數i,j定義LCP(i,j)=lcp(Suffix(SA),Suffix(SA[j])，其中i,j均為1至n的整數。LCP(i,j)也就是後綴數組中第i個和第j個後綴的最長公***前綴的長度。
關於LCP有兩個顯而易見的性質：
性質2.1 LCP(i,j)=LCP(j,i)
性質2.2 LCP(i,i)=len(Suffix(SA))=n-SA+1
這兩個性質的用處在於，我們計算LCP(i,j)時只需要考慮i<j的情況，因為i>j時可交換i,j，i=j時可以直接輸出結果n-SA+1。
直接根據定義，用順次比較對應字符的方法來計算LCP(i,j)顯然是很低效的，時間復雜度為O(n)，所以我們必須進行適當的預處理以降低每次計算LCP的復雜度。
經過仔細分析，我們發現LCP函數有壹個非常好的性質：
設i<j，則LCP(i,j)=min{LCP(k-1,k)|i+1≤k≤j} （LCP Theorem）
要證明LCP Theorem，首先證明LCP Lemma:
對任意1≤i<j<k≤n，LCP(i,k)=min{LCP(i,j),LCP(j,k)}
證明：設p=min{LCP(i,j),LCP(j,k)}，則有LCP(i,j)≥p,LCP(j,k)≥p。
設Suffix(SA)=u,Suffix(SA[j])=v,Suffix(SA[k])=w。
由u=LCP(i,j)v得u=pv；同理v=pw。
於是Suffix(SA)=pSuffix(SA[k])，即LCP(i,k)≥p。 (1)
又設LCP(i,k)=q>p，則
u[1]=w[1],u[2]=w[2],...u[q]=w[q]。
而min{LCP(i,j),LCP(j,k)}=p說明u[p+1]≠v[p+1]或v[p+1]≠w[q+1]，
設u[p+1]=x,v[p+1]=y,w[p+1]=z，顯然有x≤y≤z，又由p<q得p+1≤q，應該有x=z，也就是x=y=z，這與u[p+1]≠v[p+1]或v[p+1]≠w[q+1]矛盾。
於是，q>p不成立，即LCP(i,k)≤p。 (2)
綜合(1),(2)知 LCP(i,k)=p=min{LCP(i,j),LCP(j,k)}，LCP Lemma得證。
於是LCP Theorem可以證明如下：
當j-i=1和j-i=2時，顯然成立。
設j-i=m時LCP Theorem成立，當j-i=m+1時，
由LCP Lemma知LCP(i,j)=min{LCP(i,i+1),LCP(i+1,j)}，
因j-(i+1)≤m，LCP(i+1,j)=min{LCP(k-1,k)|i+2≤k≤j}，故當j-i=m+1時，仍有
LCP(i,j)=min{LCP(i,i+1),min{LCP(k-1,k)|i+2≤k≤j}}=min{LCP(k-1,k}|i+1≤k≤j)
根據數學歸納法，LCP Theorem成立。
根據LCP Theorem得出必然的壹個推論：
LCP Corollary 對i≤j<k，LCP(j,k)≥LCP(i,k)。
定義壹維數組height，令height=LCP(i-1,i)，1<i≤n，並設height[1]=0。
由LCP Theorem，LCP(i,j)=min{height[k]|i+1≤k≤j}，也就是說，計算LCP(i,j)等同於詢問壹維數組height中下標在i+1到j範圍內的所有元素的最小值。如果height數組是固定的，這就是非常經典的RMQ（Range Minimum Query）問題。
RMQ問題可以用線段樹或靜態排序樹在O(nlogn)時間內進行預處理，之後每次詢問花費時間O(logn)，更好的方法是RMQ標準算法，可以在O(n)時間內進行預處理，每次詢問可以在常數時間內完成。
對於壹個固定的字符串S，其height數組顯然是固定的，只要我們能高效地求出height數組，那麽運用RMQ方法進行預處理之後，每次計算LCP(i,j)的時間復雜度就是常數級了。於是只有壹個問題——如何盡量高效地算出height數組。
根據計算後綴數組的經驗，我們不應該把n個後綴看作互不相關的普通字符串，而應該盡量利用它們之間的聯系，下面證明壹個非常有用的性質：
為了描述方便，設h=height[Rank]，即height=h[SA]。h數組滿足壹個性質：
性質3 對於i>1且Rank>1，壹定有h≥h[i-1]-1。
為了證明性質3，我們有必要明確兩個事實：
設i<n,j<n，Suffix(i)和Suffix(j)滿足lcp(Suffix(i),Suffix(j)>1，則成立以下兩點：
Fact 1 Suffix(i)<Suffix(j) 等價於 Suffix(i+1)<Suffix(j+1)。
Fact 2 壹定有lcp(Suffix(i+1),Suffix(j+1))=lcp(Suffix(i),Suffix(j))-1。
看起來很神奇，但其實很自然：lcp(Suffix(i),Suffix(j))>1說明Suffix(i)和Suffix(j)的第壹個字符是相同的，設它為α，則Suffix(i)相當於α後連接Suffix(i+1)，Suffix(j)相當於α後連接Suffix(j+1)。比較Suffix(i)和Suffix(j)時，第壹個字符α是壹定相等的，於是後面就等價於比較Suffix(i)和Suffix(j)，因此Fact 1成立。Fact 2可類似證明。
於是可以證明性質3：
當h[i-1]≤1時，結論顯然成立，因h≥0≥h[i-1]-1。
當h[i-1]>1時，也即height[Rank[i-1]]>1，可見Rank[i-1]>1，因height[1]=0。
令j=i-1,k=SA[Rank[j]-1]。顯然有Suffix(k)<Suffix(j)。
根據h[i-1]=lcp(Suffix(k),Suffix(j))>1和Suffix(k)<Suffix(j)：
由Fact 2知lcp(Suffix(k+1),Suffix(i))=h[i-1]-1。
由Fact 1知Rank[k+1]<Rank，也就是Rank[k+1]≤Rank-1。
於是根據LCP Corollary，有
LCP(Rank-1,Rank)≥LCP(Rank[k+1],Rank)
=lcp(Suffix(k+1),Suffix(i))
=h[i-1]-1
由於h=height[Rank]=LCP(Rank-1,Rank)，最終得到 h≥h[i-1]-1。
根據性質3，可以令i從1循環到n按照如下方法依次算出h：
若Rank=1，則h=0。字符比較次數為0。
若i=1或者h[i-1]≤1，則直接將Suffix(i)和Suffix(Rank-1)從第壹個字符開始依次比較直到有字符不相同，由此計算出h。字符比較次數為h+1，不超過h-h[i-1]+2。
否則，說明i>1，Rank>1，h[i-1]>1，根據性質3，Suffix(i)和Suffix(Rank-1)至少有前h[i-1]-1個字符是相同的，於是字符比較可以從h[i-1]開始，直到某個字符不相同，由此計算出h。字符比較次數為h-h[i-1]+2。
設SA[1]=p，那麽不難看出總的字符比較次數不超過
也就是說，整個算法的復雜度為O(n)。
求出了h數組，根據關系式height=h[SA]可以在O(n)時間內求出height數組，於是
可以在O(n)時間內求出height數組。
結合RMQ方法，在O(n)時間和空間進行預處理之後就能做到在常數時間內計算出對任意(i,j)計算出LCP(i,j)。
因為lcp(Suffix(i),Suffix(j))=LCP(Rank,Rank[j])，所以我們也就可以在常數時間內求出S的任何兩個後綴之間的最長公***前綴。這正是後綴數組能強有力地處理很多字符串問題的重要原因之壹。