在字符串處理中，後綴樹和後綴數組是非常強大的工具，其中後綴樹是眾所周知的，而後綴數組在國內的資料中很少見到。事實上，後綴數組是後綴樹的壹個非常微妙的替代品。它比後綴樹更容易編程實現，可以用較少的時間復雜度實現後綴樹的很多功能。而且比後綴樹占用的空間小很多。可以說後綴數組在信息學奧數中比後綴樹更實用。因此，在本文中，筆者想介紹後綴數組的基本概念和構造方法，以及後綴數組的最長公共前綴數組的構造方法，最後結合壹些例子談談後綴數組的應用。
基本概念
首先，明確壹些必要的定義:
字符集A字符集∑是壹個具有全序關系的集合，即∑中任意兩個不同的元素α和β在大小上可以比較，或者α
String A string 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到整個字符串末尾的特殊子串。從I開始的字符串S的後綴表示為suffix (s，I)，即Suffix(S，I) = s [I...鏡頭。
字符串大小的比較是指所謂的“字典序”比較，即對於兩個字符串U和V，讓我從1開始依次比較U和V，如果相等，讓我加1，否則，如果U
從字符串大小比較的定義來看，S起始位置不同的兩個後綴U和V的比較結果不可能相等，因為這裏不能滿足u=v，len(u)=len(v)的必要條件。
我們約定壹個字符集∑和壹個字符串S，設len(S)=n，S[n]='$ '，也就是說，S以壹個特殊字符' $ '結尾，' $ '小於∑中的任何壹個字符。除S[n]外，S中的所有字符都屬於∑。對於約定的字符串S，從位置I開始的後綴直接寫成後綴(I)，省略參數S。
後綴數組後綴數組SA是壹維數組，保存1的某種排列...n，SA[1]，SA[2]，...SA[n]，並保證後綴(SA)
Rank數組Rank array = SA-1，也就是說，如果SA=j，Rank[j]=i，不難看出，Rank保存了後綴(I)在所有後綴中從小到大的“秩”。
施工方法
如何構造後綴數組？最直接簡單的方法當然是把s的後綴當做壹些普通的字符串，按照壹般的字符串排序方法從小到大排序。
不難看出，這種方法比較笨拙，因為沒有利用後綴之間的有機聯系，所以效率不可能很高。即使使用多鍵快速排序，最壞情況下的時間復雜度仍然是O(n2)，滿足不了我們的需求。
下面介紹加倍算法，該算法充分利用後綴之間的關系，成功地將構造後綴數組的最壞時間復雜度降低到O(nlogn)。
對於壹個字符串u，我們定義u的k前綴。
定義k前綴比較關系
設兩根弦u和v，
u & ltKv當且僅當英國
U=kv當且僅當uk=vk
U≤kv當且僅當uk≤vk。
直觀地說，這些帶有下標k的比較符號的意義是按照字典順序比較兩個字符串的前k個字符。特別的壹點是，在比較大於和小於的時候，壹個字符串的長度小於k並不重要，只要第壹個字符串大於或小於第二個字符串，k個字符的比較就結束了。
根據前綴比較器的性質，我們可以得到以下非常重要的性質:
對於k≥n，後綴(I)的性質1.1
屬性1.2後綴(i)=2kSuffix(j)相當於
後綴(i)=kSuffix(j)和後綴(i+k)=kSuffix(j+k)。
屬性1.3後綴(i) < 2kSuffix(j)相當於
後綴(I)& lt；KS(j) or(後綴(i)=kSuffix(j)和後綴(I+k)
這裏有個問題，當I+k >；n或j+k & gt；後綴(i+k)或後綴(j+k)是n時沒有明確定義的表達式，但實際上並不需要考慮這個問題，因為此時後綴(I)或後綴(j)的長度沒有超過k，即它們的k前綴都以' $ '結尾，所以k前綴比較的結果不能相等，即前k個字符。
k後綴數組SAk被定義為存儲1的某種排列...n SAK [1]，SAK [2]，...SAK [n]使得後綴(SAK) ≤ KSuffix (SAK [I+1])，1 ≤ n .也就是說，在k-前綴比較關系下，所有後綴從小到大排序，排序後的後綴的起始位置依次放入數組SAk中。
定義k秩數組Rankk，表示k前綴關系下後綴(I)從小到大的秩，即1加後綴(j)
假設我們已經找到了SAk和Rankk，那麽我們就很容易找到SA2k和Rank2k，因為根據1.2和1.3的性質，2k前綴的比較關系可以通過組合壹個常數個k前綴的比較關系來等價表示，而Rankk數組實際上給出了
後綴(I)& lt；當且僅當秩為k
後綴(i)=kSuffix(j)當且僅當Rankk=Rankk[j]
所以比較k-前綴比較關系下後綴(I)和後綴(j)的大小可以在壹個常數時間內完成，所以對≤k關系下的所有後綴進行排序和壹般排序沒什麽區別，實際上相當於每個後綴(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。這個問題很簡單:因為
因此，我們可以在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)的過程，所以
後綴數組SA和秩數組可以在O(nlogn)時間內計算。
最長公共前綴
現在字符串S的後綴數組SA可以在O(nlogn)時間內計算出來。有了SA，我們已經可以做很多事情了，比如O(mlogn)時間的模式匹配，其中m和n分別是模式串和要匹配的串的長度。但是為了充分發揮後綴數組的威力，我們需要計算壹個輔助工具——最長常用前綴。
函數LCP (u，v) = max {i | u = iv}是為兩個字符串u和v定義的，即從開始依次比較u和v的對應字符，對應字符連續相等的最大位置稱為這兩個字符串的最長公共前綴。
對於正整數I和J，LCP (i，j) = LCP(後綴(SA)，後綴(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(後綴(sa)) = n-sa+1。
這兩個性質的用途是我們只需要考慮I < J，因為i & gtj可互換時，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理論)。
要證明LCP定理，先證明LCP引理:
對於任何1 ≤ I
證明:設p=min{LCP(i，j)，LCP (j，k)}，則有LCP(i，j) ≥ p，LCP(j，k) ≥ p。
設後綴(sa) = u，後綴(sa [j]) = v，後綴(sa [k]) = w。
U = PV from u=LCP(i，j)v；同理，v=pw。
So後綴(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+65438]。
設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不同
所以，q & gtp不成立，即LCP (I，k) ≤ p. (2)
綜合(1)，(2)知道LCP (I，k) = p = min {LCP (I，j)，LCP (j，k)}，LCP引理的證明。
那麽LCP定理可以證明如下:
當j-i=1，j-i=2時，顯然成立。
設j-i=m，LCP定理成立，當j-i=m+1時，
由LCP引理可知，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+65438+時。
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定理。
根據LCP定理，得出壹個必然的推論:
LCP推論對I ≤ j有負面影響
定義壹維數組高度，使height=LCP(i-1，I)，1
從LCP定理可知，LCP(i，j)= min { height[k]| i+1≤k≤j }，也就是說，計算LCP (i，j)相當於在壹維數組的高度中，求下標在I+1到j範圍內的所有元素的最小值。如果高度數組是固定的，這是壹個非常經典的RMQ(範圍最小查詢)問題。
RMQ問題可以通過線樹或靜態排序樹在O(nlogn)時間內進行預處理，然後每次查詢需要O(logn)時間。比較好的方法是RMQ標準算法，可以在O(n)時間內進行預處理，每次查詢可以在壹個常數時間內完成。
對於壹個固定的字符串S，它的高度數組顯然是固定的。只要我們能高效地得到高度數組，在用RMQ方法進行預處理後，每次計算LCP(i，j)的時間復雜度是常數。所以只有壹個問題——如何盡可能高效地計算高度數組。
根據計算後綴數組的經驗，不要把n個後綴看成不相關的普通字符串，而要盡量利用它們之間的關系。以下是壹個非常有用的屬性:
為了描述方便，設h=height[Rank]，即height=h[SA]。h數組滿足壹個屬性:
i & gt的屬性3；1且秩>；1，必須有h≥h[i-1]-1。
為了證明性質3，我們有必要澄清兩個事實:
設I < n，j & ltn，後綴(I)和後綴(j)滿足LCP(後綴(I)，後綴(j)>；1，以下兩點成立:
事實1後綴(I)& lt；後綴(j)等價於後綴(I+1)<後綴(j+1).
事實2必須有LCP(後綴(I+1)，後綴(J+1)) = LCP(後綴(I)，後綴(j))-1。
看起來很神奇，其實很自然:lcp(後綴(I)，後綴(j))& gt；1表示後綴(I)和後綴(j)的第壹個字符相同。設它是α，那麽後綴(I)等價於α後跟後綴(i+1)，後綴(j)等價於α後跟後綴(j+1)。比較後綴(I)和後綴(j)時，第壹個字符α必須相等，所以下面等價於比較後綴(I)和後綴(j)，所以事實1成立。事實2同樣可以證明。
因此，性質3可以被證明:
當h[i-1]≤1時，結論明顯成立，因為h≥0≥h[i-1]-1。
當h [I-1] >: 1，即height[Rank[i-1]]>時；1，顯示等級[i-1]>1，因為高度[1]=0。
設j = I-1，k = sa[秩[j]-1]。顯然有後綴(k)<後綴(j).
根據h [I-1] = LCP(後綴(k)，後綴(j)) > 1和後綴(k)<後綴(j):
LCP(後綴(k+1)，後綴(I)) = h [I-1]-1。
從事實1 < Rank知道rank [k+1]，即Rank[k+1]≤Rank-1。
所以根據LCP推論，有
LCP(秩-1，秩)≥LCP(秩[k+1]，秩)
=lcp(後綴(k+1)，後綴(I))
=h[i-1]-1
因為H = height[rank]= LCP(rank-1，rank)，所以最終得到h≥h[i-1]-1。
根據性質3，I可以從1循環到n，H可以依次計算如下:
如果秩=1，那麽h=0。字符比較的次數為0。
如果i=1或者h[i-1]≤1，那麽直接從第壹個字符開始比較後綴(I)和後綴(Rank-1)，直到有不同的字符為止，從而計算出H..字符比較數為h+1，不超過h-h[i-1]+2。
否則，我& gt1，Rank & gt1，h[i-1]>1，根據性質3，後綴(I)和後綴(Rank-1)至少有第壹個h[i-1]-1字符相同，所以字符比較可以從h[i-1]開始，直到某壹個。字符比較次數為h-h[i-1]+2。
設SA[1]=p，那麽不難看出字符比較的總數不超過。
換句話說，整個算法的復雜度是O(n)。
得到h數組，根據關系height=h[SA]可以在O(n)時間內得到高度數組，所以
可以在O(n)時間內找到高度數組。
結合RMQ方法，對O(n)時間和空間進行預處理後，可以計算出常數時間內任意(I，j)的LCP (i，j)。
因為LCP (suffix (I)，suffix (j)) = LCP (rank，rank [j])，所以我們也可以在壹個常數時間內找到S的任意兩個後綴之間最長的公共前綴。這也是後綴數組能夠有力處理很多字符串問題的重要原因之壹。