2.4　后綴數組

前面曾經提到過Aho-Corasick自動機算法，用以解決多模板匹配問題。其前提是需要事先知道所有的模板，但在實際應用中，無法事先知道查詢內容，比如在搜索引擎中，每次的查詢是不可能直接預處理出來的，這就需要預處理文本串而非每次的查詢內容。

后綴數組是處理字符串的有力工具。后綴數組是后綴樹的一個非常精巧的替代品。它比后綴樹容易編程實現，能夠實現后綴樹的很多功能，時間復雜度也并不遜色，而且比后綴樹所占用的內存空間小很多。可以說，在信息學競賽中，后綴數組比后綴樹更為實用。本節首先介紹構造后綴數組的方法，重點介紹如何用簡潔高效的代碼實現后綴數組；接著介紹后綴數組在各種類型題目中的具體應用。

2.4.1　后綴數組基本原理

首先定義兩個概念：

（1）后綴數組：后綴數組sa是一個一維數組，它保存1，…，n的某個排列sa[1]，sa[2]，…，sa[n]，并且保證suffix（sa[i]）< suffix（sa[i+1]），1≤i<n。也就是將sa的n個后綴從小到大進行排序之后，把排好序的后綴的開頭位置順次放入sa數組中。

（2）名次數組：名次數組rank[i]保存的是suffix（i）在所有后綴中從小到大排列的“名次”，如圖2.9所示。

簡單來說，后綴數組是“排第幾的是誰？”，名次數組是“排第幾？”。容易看出，后綴數組和名次數組為互逆運算。

設字符串的長度為n，為了方便比較大小，可以在字符串后面添加一個字符，這個字符沒有在前面的字符中出現過，而且比前面的字符都要小。在求出名次數組后，可以僅用O（1）的時間比較任意兩個后綴的大小。在求出后綴數組或名次數組中的其中一個后，便可以用O（n）的時間求出另外一個。

下面介紹一種常用的用來實現后綴數組的倍增算法。

倍增算法的主要思路是用倍增的方法對每個字符開始的長度為2k的子字符串進行排序，求出排名，即rank值。k從0開始，每次加1，當2k大于n以后，從每個字符開始的長度為2k的子字符串就相當于所有的后綴，并且這些子字符串都已經比較出了大小，即rank值中沒有相同的值，那么此時的rank值就是最后的結果。每一次排序都利用上次長度為2k-1的字符串的rank值，那么長度為2k的字符串就可以用兩個長度為2k-1字符串的排名作為關鍵字來表示，然后進行基數排序，便得出了長度為2k字符串的rank值。以字符串“aabaaaab”為例，整個過程如圖2.10所示，其中，x、y是表示長度為2k的字符串的兩個關鍵字。

后綴數組倍增算法的實現如下所述。

待排序的字符串放在r數組中，從r[0]到r[n-1]，長度為n，且最大值小于m。為了函數操作的方便，約定除r[n-1]外的所有r[i]都大于0，r[n-1]=0。函數結束后，結果放在sa數組中，從sa[0]到sa[n-1]。

函數的第一步，要對長度為1的字符串進行排序。一般來說，在字符串的題目中，r的最大值不會很大，所以使用了基數排序。如果r的最大值很大，那么就把這段代碼改成快速排序。代碼如下所述。

x數組保存的值相當于是rank值。下面的操作只是用x數組比較字符的大小，所以沒有必要求出當前真實的rank值。

接下來進行若干次基數排序，在實現的時候，有一個優化。基數排序要分兩次，第一次是對第二關鍵字排序，第二次是對第一關鍵字排序。對第二關鍵字排序的結果實際上可以利用上一次求得的sa直接算出，沒有必要再算一次，其代碼如下所述。

其中，變量j是當前字符串的長度，數組y保存的是對第二關鍵字排序的結果，然后對第一關鍵字進行排序，其代碼如下所述。

這樣求出了新的sa值。在求出sa值后，下一步是計算rank值。要注意的是，可能有多個字符串的rank值是相同的，所以必須比較兩個字符串是否完全相同，y數組的值已經沒有必要保存，為了節省空間，用y數組保存rank值。有一個優化，將x和y定義為指針類型，復制整個數組的操作可以用交換指針的值代替，不必逐個地復制數組中的值，其代碼如下所述。

其中，cmp函數的代碼如下。

規定r[n-1]=0的優點在于如果r[a]=r[b]，說明以r[a]或r[b]開頭的長度為l的子串肯定不包括r[n-1]，所以調用變量r[a+l]和r[b+l]不會導致數組下標越界，就不需要做特殊判斷。執行完上面的代碼后，rank值保存在x數組中，而變量p的結果實際上就是不同的子串的個數。可以優化，如果p等于n，那么函數可以結束。因為在當前長度的字符串中，已經沒有相同的字符串，接下來的排序不會改變rank值。對上面的兩段代碼，循環的初始賦值和終止條件如下所述。

在第一次排序以后，rank數組中的最大值小于p，所以令m=p。整個倍增算法基本寫好，代碼大約25行。倍增算法的時間復雜度為每次基數排序的時間復雜度O（n），排序的次數取決于最長公共子串的長度。最壞的情況下，排序次數為logn次，所以總的時間復雜度為O（nlogn）。

2.4.2　后綴數組的應用

先介紹后綴數組的一些性質。

height數組：定義height[i]=suffix（sa[i-1]）和suffix（sa[i]）的最長公共前綴，也就是排名相鄰的兩個后綴的最長公共前綴。那么對于j和k，不妨設rank[j]<rank[k]，則有以下性質。

suffix（j）和suffix（k）的最長公共前綴為height[rank[j]+1]，height[rank[j]+2]，height[rank[j]+3]，…，height[rank[k]]中的最小值。

例如，字符串為“aabaaaab”，求后綴“abaaaab”和后綴“aaab”的最長公共前綴，如圖2.11所示。

那么應該如何高效地求出height值呢？

如果按height[2]，height[3]，…，height[n]的順序計算，最壞情況下的時間復雜度為O（n2），而沒有利用字符串的性質。定義h[i]=height[rank[i]]，也就是suffix（i）和在它前一名的后綴的最長公共前綴。

h[]數組有以下性質：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）。

例1：最長公共前綴。給定一個字符串，詢問某兩個后綴的最長公共前綴。

算法分析：按照上面所說的做法，求兩個后綴的最長公共前綴可以轉化為求某個區間上的最小值。對于這個RMQ（Range Minimum Query）問題，可以用O（nlogn）的時間先預處理，以后每次回答詢問的時間復雜度為O（1）。所以預處理的時間復雜度為O（nlogn），每次回答詢問的時間復雜度為O（1）。如果RMQ問題用O（n）的時間復雜度預處理，那么本問題預處理的時間復雜度可以做到O（n）。

例2：可重疊最長重復子串。給定一個字符串，求最長重復子串，這兩個子串可以重疊。

算法分析：這道題是后綴數組的一個簡單應用，算法比較簡單，只需要求height數組里的最大值即可。首先求最長重復子串，等價于求兩個后綴的最長公共前綴的最大值。因為任意兩個后綴的最長公共前綴都是height數組里某一段的最小值，那么這個值一定不大于height數組里的最大值，所以最長重復子串的長度就是height數組里的最大值。這個算法的時間復雜度為O（n）。

例3：不可重疊最長重復子串。給定一個字符串，求最長重復子串，這兩個子串不能重疊。

算法分析：這題比上一題稍復雜一點。先二分答案，把題目變成判定性問題，判斷是否存在兩個長度為k的子串是相同的，且不重疊。解決這個問題的關鍵還是利用height數組，把排序后的后綴分成若干組。其中每組后綴之間的height值都不小于k。例如，字符串為“aabaaaab”，當k=2時，后綴分成了4組，如圖2.12所示。

容易看出，有希望成為最長公共前綴且不小于k的兩個后綴一定在同一組中。對于每組的后綴，只需要判斷每個后綴的sa值的最大值和最小值之差是否不小于k。如果有一組滿足，則說明存在，否則不存在。算法的時間復雜度為O（nlogn）。本題中利用height值對后綴進行分組的方法很常用。

例4：可重疊的k次最長重復子串。給定一個字符串，求至少出現k次的最長重復子串，k個子串可以重疊。

算法分析：先二分答案，然后將后綴分成若干組，判斷有沒有一個組的后綴個數不小于k。如果有，那么存在k個相同的子串滿足條件，否則不存在。算法的時間復雜度為O（nlogn）。

例5：不相同子串的個數。給定一個字符串，求不相同的子串的個數。

算法分析：每個子串一定是某個后綴的前綴，那么原問題等價于求所有后綴之間的不相同的前綴的個數。如果所有的后綴按照suffix（sa[1]），suffix（sa[2]），suffix（sa[3]），…，suffix（sa[n]）的順序計算，不難發現，對于每一次新加進來的后綴suffix（sa[k]），它將產生n-sa[k]+1個新的前綴，但其中有height[k]個和前面的字符串的前綴是相同的，所以suffix（sa[k]）將“貢獻”出n-sa[k]+1-height[k]個不同的子串，累加后便是原問題的答案。算法時間復雜度為O（n）。

2.4.3　例題講解

例2-4　Distinct Substrings

Time Limit:2000/1000 ms（Java/Others）　Memory Limit:131072/131072 KB（Java/Others）

題目描述：

給定一個字符串，需要找出所有的不同的子串。

輸入：

第一行輸入測試數據T（≤20）組，接下來在每行中包括一個字符串（字符串長度不超過1000）。

輸出：

對于每組數據，都要輸出一行，并包含一個整數，該整數表示該字符串有多少個不同的子串。

樣例輸入：

2

CCCCC

ABABA

樣例輸出：

5

9

題目來源：SPO J694。

解題思路：

一個字符串中不同子串的總數為∑（len-height[i]-sa[i]）。

題目實現：

例2-5　Musical Theme

Time Limit:2000/1000 ms（Java/Others）　Memory Limit:131072/131072 KB（Java/Others）

題目描述：

用N（1≤N≤20000）個音符的序列來表示一首樂曲，每個音符都是1～88范圍內的整數，現在要找一個重復的主題。主題是整個音符序列的一個子串，需要滿足如下條件：

（1）長度至少為5個音符。

（2）在樂曲中重復出現（可能經過轉調，轉調的意思是在主題序列的每個音符上都加上或減去同一個整數值）。

（3）重復出現的同一主題不能有公共部分，即給出一串字符，求不重合的最長重復子串，并且長度大于要求的5。

輸入：

輸入數據有多組，每組數據的第一行輸入一個整數N，在接下來一行中的N個整數表示音符序列，最后一組測試數據以0結束。

輸出：

對于每組數據，都要輸出一行并包含一個整數，該整數表示該字符串滿足條件的最長重復子串長度。

樣例輸入：

30

25 27 30 34 39 45 52 60 69 79 69 60 52 45 39 34 30 26 22 18

82 78 74 70 66 67 64 60 65 80

0

樣例輸出：

5

題目來源：POJ 1743。

解題思路：

將height值分組，然后記錄在二分答案時滿足height值不小于p的sa[i]的最大、最小值，如果最大值減去最小值不小于p，就說明兩個子串的lcp值不小于p，并且它們的坐標也相差不小于p。另外，轉調的影響可通過求相鄰序列的差值解決。

題目實現：