為生存而奔跑

IOI2004國家集訓(xùn)隊論文 許智磊
第 1 頁 共11頁
后 綴 數(shù) 組
安徽省蕪湖市第一中學(xué) 許智磊
【摘要】
本文介紹后綴數(shù)組的基本概念、方法以及應(yīng)用。
首先介紹O(nlogn)復(fù)雜度構(gòu)造后綴數(shù)組的倍增算法，接著介紹了配合后綴
數(shù)組的最長公共前綴 LCP（Longest Common Prefix）的計算方法，并給出一個
線性時間內(nèi)計算height 數(shù)組（記錄跨度為1 的LCP 值的數(shù)組）的算法。為了讓
讀者對如何運用后綴數(shù)組有一個感性認(rèn)識，還介紹了兩個應(yīng)用后綴數(shù)組的例子：
多模式串的模式匹配（給出每次匹配O(m+logn)時間復(fù)雜度的算法）以及求最
長回文子串（給出O(nlogn)時間復(fù)雜度的算法）。最后對后綴數(shù)組和后綴樹作了
一番比較。
【關(guān)鍵字】
字符串 后綴 k-前綴比較關(guān)系
后綴數(shù)組 名次數(shù)組 后綴樹 倍增算法 基數(shù)排序
最長公共前綴 RMQ問題 模式匹配 回文串 最長回文子串
【正文】
在字符串處理當(dāng)中，后綴樹和后綴數(shù)組都是非常有力的工具，其中后綴樹
大家了解得比較多，關(guān)于后綴數(shù)組則很少見于國內(nèi)的資料。其實后綴數(shù)組是后
綴樹的一個非常精巧的替代品，它比后綴樹容易編程實現(xiàn)，能夠?qū)崿F(xiàn)后綴樹的
很多功能而時間復(fù)雜度也不太遜色，并且，它比后綴樹所占用的空間小很多。
可以說，在信息學(xué)競賽中后綴數(shù)組比后綴樹要更為實用。因此在本文中筆者想
介紹一下后綴數(shù)組的基本概念、構(gòu)造方法，以及配合后綴數(shù)組的最長公共前綴
數(shù)組的構(gòu)造方法，最后結(jié)合一些例子談?wù)労缶Y數(shù)組的應(yīng)用。
IOI2004國家集訓(xùn)隊論文 許智磊
第 2 頁 共11頁
基本概念
首先明確一些必要的定義：
字符集 一個字符集Σ是一個建立了全序關(guān)系的集合，也就是說，Σ中
的任意兩個不同的元素α 和β 都可以比較大小，要么α<β，要么β<α（也就是
α>β）。字符集Σ中的元素稱為字符。
字符串 一個字符串S 是將n 個字符順次排列形成的數(shù)組，n 稱為S 的
長度，表示為len(S)。S 的第i個字符表示為S[i]。
子串 字符串S 的子串S[i..j]，i≤j，表示S 串中從i 到j(luò) 這一段，也就
是順次排列S[i],S[i+1],...,S[j]形成的字符串。
后綴 后綴是指從某個位置i 開始到整個串末尾結(jié)束的一個特殊子串。
字符串S 的從i開頭的后綴表示為Suffix(S,i)，也就是Suffix(S,i)=S[i..len(S)]。
關(guān)于字符串的大小比較，是指通常所說的“字典順序”比較，也就是對于
兩個字符串u、v，令i 從1 開始順次比較u[i]和v[i]，如果u[i]=v[i]則令i 加1，
否則若u[i]<v[i]則認(rèn)為u<v，u[i]>v[i]則認(rèn)為u>v（也就是v<u），比較結(jié)束。如
果i>len(u)或者i>len(v)仍比較出結(jié)果，那么若len(u)<len(v)則認(rèn)為u<v，若
len(u)=len(v)則認(rèn)為u=v，若len(u)>len(v)則u>v。
從字符串的大小比較的定義來看，S 的兩個開頭位置不同的后綴u 和v 進行
比較的結(jié)果不可能是相等，因為u=v 的必要條件len(u)=len(v)在這里不可能滿
足。
下面我們約定一個字符集Σ和一個字符串S，設(shè)len(S)=n，且S[n]='$'，也
就是說S 以一個特殊字符'$'結(jié)尾，并且'$'小于Σ中的任何一個字符。除了S[n]
之外，S 中的其他字符都屬于Σ。對于約定的字符串S，從位置i 開頭的后綴直
接寫成Suffix(i)，省去參數(shù)S。
后綴數(shù)組 后綴數(shù)組SA 是一個一維數(shù)組，它保存1..n 的某個排列
SA[1],SA[2],...SA[n]，并且保證 Suffix(SA[i])<Suffix(SA[i+1]),1≤i<n。也就是將
S 的n 個后綴從小到大進行排序之后把排好序的后綴的開頭位置順次放入SA
中。
名次數(shù)組 名次數(shù)組Rank=SA-1，也就是說若SA[i]=j，則Rank[j]=i，不難
看出Rank[i]保存的是Suffix(i)在所有后綴中從小到大排列的“名次”。
構(gòu)造方法
如何構(gòu)造后綴數(shù)組呢？最直接最簡單的方法當(dāng)然是把S 的后綴都看作一些
普通的字符串，按照一般字符串排序的方法對它們從小到大進行排序。
不難看出，這種做法是很笨拙的，因為它沒有利用到各個后綴之間的有機
聯(lián)系，所以它的效率不可能很高。即使采用字符串排序中比較高效的Multi-key
Quick Sort，最壞情況的時間復(fù)雜度仍然是O(n2)的，不能滿足我們的需要。
IOI2004國家集訓(xùn)隊論文 許智磊
第 3 頁 共11頁
下面介紹倍增算法(Doubling Algorithm)，它正是充分利用了各個后綴之間的
聯(lián)系，將構(gòu)造后綴數(shù)組的最壞時間復(fù)雜度成功降至O(nlogn)。
對一個字符串u，我們定義u的k-前綴
î í ì
<
³
=
u len u k
u k len u k
u k
, ( )
[1 .. ] , ( )
定義k-前綴比較關(guān)系<k、=k和≤k：
設(shè)兩個字符串u 和v，
u<kv 當(dāng)且僅當(dāng) uk<vk
u=kv 當(dāng)且僅當(dāng) uk=vk
u≤kv 當(dāng)且僅當(dāng) uk≤vk
直觀地看這些加了一個下標(biāo)k 的比較符號的意義就是對兩個字符串的前k
個字符進行字典序比較，特別的一點就是在作大于和小于的比較時如果某個字
符串的長度不到k 也沒有關(guān)系，只要能夠在k 個字符比較結(jié)束之前得到第一個
字符串大于或者小于第二個字符串就可以了。
根據(jù)前綴比較符的性質(zhì)我們可以得到以下的非常重要的性質(zhì)：
性質(zhì)1.1 對k≥n，Suffix(i)<kSuffix(j) 等價于 Suffix(i)<Suffix(j)。
性質(zhì)1.2 Suffix(i)=2kSuffix(j)等價于
Suffix(i)=kSuffix(j) 且 Suffix(i+k)=kSuffix(j+k)。
性質(zhì)1.3 Suffix(i)<2kSuffix(j) 等價于
Suffix(i)<kS(j) 或 (Suffix(i)=kSuffix(j) 且 Suffix(i+k)<kSuffix(j+k))。
這里有一個問題，當(dāng)i+k>n 或者j+k>n 的時候Suffix(i+k)或Suffix(j+k)是無
明確定義的表達(dá)式，但實際上不需要考慮這個問題，因為此時Suffix(i)或者
Suffix(j)的長度不超過k，也就是說它們的k-前綴以'$'結(jié)尾，于是k-前綴比較的
結(jié)果不可能相等，也就是說前k 個字符已經(jīng)能夠比出大小，后面的表達(dá)式自然
可以忽略，這也就看出我們規(guī)定S 以'$'結(jié)尾的特殊用處了。
定義k-后綴數(shù)組SAk 保存1..n 的某個排列SAk[1],SAk[2],…SAk[n]使得
Suffix(SAk[i]) ≤kSuffix(SAk[i+1]),1≤i<n。也就是說對所有的后綴在k-前綴比較關(guān)
系下從小到大排序，并且把排序后的后綴的開頭位置順次放入數(shù)組SAk中。
定義k-名次數(shù)組Rankk，Rankk[i]代表Suffix(i)在k-前綴關(guān)系下從小到大的
“名次”，也就是1 加上滿足Suffix(j)<kSuffix(i)的j 的個數(shù)。通過SAk很容易在
O(n)的時間內(nèi)求出Rankk。
假設(shè)我們已經(jīng)求出了SAk 和Rankk，那么我們可以很方便地求出SA2k 和
Rank2k，因為根據(jù)性質(zhì)1.2 和1.3，2k-前綴比較關(guān)系可以由常數(shù)個k-前綴比較關(guān)
系組合起來等價地表達(dá)，而Rankk 數(shù)組實際上給出了在常數(shù)時間內(nèi)進行<k 和=k
比較的方法，即：
Suffix(i)<kSuffix(j) 當(dāng)且僅當(dāng) Rankk[i]<Rankk[j]
Suffix(i)=kSuffix(j) 當(dāng)且僅當(dāng) Rankk[i]=Rankk[j]
因此，比較Suffix(i)和Suffix(j)在k-前綴比較關(guān)系下的大小可以在常數(shù)時間
內(nèi)完成，于是對所有的后綴在≤k 關(guān)系下進行排序也就和一般的排序沒有什么區(qū)
別了，它實際上就相當(dāng)于每個Suffix(i)有一個主關(guān)鍵字Rankk[i]和一個次關(guān)鍵字
Rankk[i+k]。如果采用快速排序之類O(nlogn)的排序，那么從SAk和Rankk構(gòu)造
IOI2004國家集訓(xùn)隊論文 許智磊
第 4 頁 共11頁
出SA2k的復(fù)雜度就是O(nlogn)。更聰明的方法是采用基數(shù)排序，復(fù)雜度為O(n)。
求出SA2k之后就可以在O(n)的時間內(nèi)根據(jù)SA2k構(gòu)造出Rank2k。因此，從SAk
和Rankk推出SA2k和Rank2k可以在O(n)時間內(nèi)完成。
下面只有一個問題需要解決：如何構(gòu)造出SA1和Rank1。這個問題非常簡單：
因為<1，=1 和≤1 這些運算符實際上就是對字符串的第一個字符進行比較，所以
只要把每個后綴按照它的第一個字符進行排序就可以求出SA1，不妨就采用快
速排序，復(fù)雜度為O(nlogn)。
于是，可以在O(nlogn)的時間內(nèi)求出SA1和Rank1。
求出了SA1和Rank1，我們可以在O(n)的時間內(nèi)求出SA2和Rank2，同樣，
我們可以再用O(n)的時間求出SA4和Rank4，這樣，我們依次求出：
SA2和Rank2，SA4和Rank4，SA8和Rank8，……直到SAm和Rankm，其中
m=2k且m≥n。而根據(jù)性質(zhì)1.1，SAm和SA 是等價的。這樣一共需要進行l(wèi)ogn
次O(n)的過程，因此
可以在O(nlogn)的時間內(nèi)計算出后綴數(shù)組SA和名次數(shù)組Rank。
最長公共前綴
現(xiàn)在一個字符串S 的后綴數(shù)組SA 可以在O(nlogn)的時間內(nèi)計算出來。利用
SA 我們已經(jīng)可以做很多事情，比如在O(mlogn)的時間內(nèi)進行模式匹配，其中
m,n 分別為模式串和待匹配串的長度。但是要想更充分地發(fā)揮后綴數(shù)組的威力，
我們還需要計算一個輔助的工具——最長公共前綴（Longest Common Prefix）。
對兩個字符串u,v 定義函數(shù)lcp(u,v)=max{i|u=iv}，也就是從頭開始順次比較
u 和v 的對應(yīng)字符，對應(yīng)字符持續(xù)相等的最大位置，稱為這兩個字符串的最長
公共前綴。
對正整數(shù)i,j 定義LCP(i,j)=lcp(Suffix(SA[i]),Suffix(SA[j])，其中i,j 均為1 至
n 的整數(shù)。LCP(i,j)也就是后綴數(shù)組中第i 個和第j 個后綴的最長公共前綴的長
度。
關(guān)于LCP 有兩個顯而易見的性質(zhì)：
性質(zhì)2.1 LCP(i,j)=LCP(j,i)
性質(zhì)2.2 LCP(i,i)=len(Suffix(SA[i]))=n-SA[i]+1
這兩個性質(zhì)的用處在于，我們計算LCP(i,j)時只需要考慮i<j 的情況，因為
i>j時可交換i,j，i=j時可以直接輸出結(jié)果n-SA[i]+1。
直接根據(jù)定義，用順次比較對應(yīng)字符的方法來計算LCP(i,j)顯然是很低效
的，時間復(fù)雜度為O(n)，所以我們必須進行適當(dāng)?shù)念A(yù)處理以降低每次計算LCP
的復(fù)雜度。
經(jīng)過仔細(xì)分析，我們發(fā)現(xiàn)LCP 函數(shù)有一個非常好的性質(zhì)：
設(shè)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)}
證明：設(shè)p=min{LCP(i,j),LCP(j,k)}，則有LCP(i,j)≥p,LCP(j,k)≥p。
IOI2004國家集訓(xùn)隊論文 許智磊
第 5 頁 共11頁
設(shè)Suffix(SA[i])=u,Suffix(SA[j])=v,Suffix(SA[k])=w。
由u=LCP(i,j)v得u=pv；同理v=pw。
于是Suffix(SA[i])=pSuffix(SA[k])，即LCP(i,k)≥p。 (1)
又設(shè)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]，
設(shè)u[p+1]=x,v[p+1]=y,w[p+1]=z，顯然有x≤y≤z，又由p<q 得p+1≤q，
應(yīng)該有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可以證明如下：
當(dāng)j-i=1 和j-i=2 時，顯然成立。
設(shè)j-i=m時LCP Theorem成立，當(dāng)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}，故當(dāng)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)
根據(jù)數(shù)學(xué)歸納法，LCP Theorem成立。
根據(jù)LCP Theorem得出必然的一個推論：
LCP Corollary 對i≤j<k，LCP(j,k)≥LCP(i,k)。
定義一維數(shù)組height，令height[i]=LCP(i-1,i)，1<i≤n，并設(shè)height[1]=0。
由LCP Theorem，LCP(i,j)=min{height[k]|i+1≤k≤j}，也就是說，計算LCP(i,j)
等同于詢問一維數(shù)組height 中下標(biāo)在i+1 到j(luò) 范圍內(nèi)的所有元素的最小值。如
果height 數(shù)組是固定的，這就是非常經(jīng)典的RMQ（Range Minimum Query）問
題。
RMQ 問題可以用線段樹或靜態(tài)排序樹在O(nlogn)時間內(nèi)進行預(yù)處理，之后
每次詢問花費時間O(logn)，更好的方法是RMQ 標(biāo)準(zhǔn)算法，可以在O(n)時間內(nèi)
進行預(yù)處理，每次詢問可以在常數(shù)時間內(nèi)完成。
對于一個固定的字符串S，其height 數(shù)組顯然是固定的，只要我們能高效地
求出height 數(shù)組，那么運用RMQ 方法進行預(yù)處理之后，每次計算LCP(i,j)的時
間復(fù)雜度就是常數(shù)級了。于是只有一個問題——如何盡量高效地算出height 數(shù)
組。
根據(jù)計算后綴數(shù)組的經(jīng)驗，我們不應(yīng)該把n 個后綴看作互不相關(guān)的普通字
符串，而應(yīng)該盡量利用它們之間的聯(lián)系，下面證明一個非常有用的性質(zhì)：
為了描述方便，設(shè)h[i]=height[Rank[i]]，即height[i]=h[SA[i]]。h 數(shù)組滿足
一個性質(zhì)：
性質(zhì)3 對于i>1 且Rank[i]>1，一定有h[i]≥h[i-1]-1。
為了證明性質(zhì)3，我們有必要明確兩個事實：
IOI2004國家集訓(xùn)隊論文 許智磊
第 6 頁 共11頁
設(shè)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 一定有l(wèi)cp(Suffix(i+1),Suffix(j+1))=lcp(Suffix(i),Suffix(j))-1。
看起來很神奇，但其實很自然：lcp(Suffix(i),Suffix(j))>1 說明Suffix(i)和
Suffix(j)的第一個字符是相同的，設(shè)它為α，則Suffix(i)相當(dāng)于α 后連接
Suffix(i+1)，Suffix(j)相當(dāng)于α 后連接Suffix(j+1)。比較Suffix(i)和Suffix(j)時，
第一個字符α 是一定相等的，于是后面就等價于比較Suffix(i)和Suffix(j)，因此
Fact 1 成立。Fact 2 可類似證明。
于是可以證明性質(zhì)3：
當(dāng)h[i-1]≤1 時，結(jié)論顯然成立，因h[i]≥0≥h[i-1]-1。
當(dāng)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)。
根據(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[i]，也就是Rank[k+1]≤Rank[i]-1。
于是根據(jù)LCP Corollary，有
LCP(Rank[i]-1,Rank[i])≥LCP(Rank[k+1],Rank[i])
=lcp(Suffix(k+1),Suffix(i))
=h[i-1]-1
由于h[i]=height[Rank[i]]=LCP(Rank[i]-1,Rank[i])，最終得到 h[i]≥h[i-1]-1。
根據(jù)性質(zhì)3，可以令i從1 循環(huán)到n按照如下方法依次算出h[i]：
若Rank[i]=1，則h[i]=0。字符比較次數(shù)為0。
若i=1 或者h(yuǎn)[i-1]≤1，則直接將Suffix(i)和Suffix(Rank[i]-1)從第一個字符開
始依次比較直到有字符不相同，由此計算出h[i]。字符比較次數(shù)為h[i]+1，不超
過h[i]-h[i-1]+2。
否則，說明i>1，Rank[i]>1，h[i-1]>1，根據(jù)性質(zhì)3，Suffix(i)和Suffix(Rank[i]-1)
至少有前h[i-1]-1 個字符是相同的，于是字符比較可以從h[i-1]開始，直到某個
字符不相同，由此計算出h[i]。字符比較次數(shù)為h[i]-h[i-1]+2。
設(shè)SA[1]=p，那么不難看出總的字符比較次數(shù)不超過
h p p h n n p n
h h i h i h p h i h i
n
i p
p
i
1 [ 1] 2( 2) [ ] 2 2( ) 4
[1] 1 ( [ ] [ 1] 2) [ 1] ( [ ] [ 1] 2)
1
1
2
£ + - + - + + + - £
+ +å - - + + + + å - - +
= +
-
=
也就是說，整個算法的復(fù)雜度為O(n)。
求出了h 數(shù)組，根據(jù)關(guān)系式height[i]=h[SA[i]]可以在O(n)時間內(nèi)求出height
數(shù)組，于是
可以在O(n)時間內(nèi)求出height 數(shù)組。
IOI2004國家集訓(xùn)隊論文 許智磊
第 7 頁 共11頁
結(jié)合RMQ 方法，在O(n)時間和空間進行預(yù)處理之后就能做到在常數(shù)時間
內(nèi)計算出對任意(i,j)計算出LCP(i,j)。
因為lcp(Suffix(i),Suffix(j))=LCP(Rank[i],Rank[j])，所以我們也就可以在常數(shù)
時間內(nèi)求出S 的任何兩個后綴之間的最長公共前綴。這正是后綴數(shù)組能強有力
地處理很多字符串問題的重要原因之一。
后綴數(shù)組的應(yīng)用
下面結(jié)合兩個例子談?wù)勅绾芜\用后綴數(shù)組。
例一 多模式串的模式匹配問題
給定一個固定待匹配串S，長度為n，然后每次輸入一個模式串P，長度為
m，要求返回P 在S 中的一個匹配或者返回匹配失敗。所謂匹配指某個位置i
滿足1≤i≤n-m+1 使得S[i..(i+m-1)]=P，也即Suffix(i)=mP。
我們知道，如果只有一個模式串，最好的算法就是KMP 算法，時間復(fù)雜
度為O(n+m)，但是如果有多個模式串，我們就要考慮做適當(dāng)?shù)念A(yù)處理使得對每
個模式串進行匹配所花的時間小一些。
最簡單的預(yù)處理莫過于建立S 的后綴數(shù)組（先在S 的后面添加'$'），然后每
次尋找匹配轉(zhuǎn)化為用二分查找法在SA 中找到和P 的公共前綴最長的一個后綴，
判斷這個最長的公共前綴是否等于m。
這樣，每次比較P 和一個后綴的復(fù)雜度為O(m)，因為最壞情況下可能比較
了m 個字符。二分查找需要調(diào)用比較的次數(shù)為O(logn)，因此總復(fù)雜度為
O(mlogn)，于是每次匹配的復(fù)雜度從O(n+m)變?yōu)镺(mlogn)，可以說改進了不
少。
可是這樣仍然不能令我們滿足。前面提到LCP 可以增加后綴數(shù)組的威力，
我們來試試用在這個問題上。
我們分析原始的二分查找算法，大體有以下幾步：
Step 1 令left=1,right=n,max_match=0。
Step 2 令mid=(left+right)/2（這里“/”表示取整除法）。
Step 3 順次比較Suffix(SA[mid])和P 的對應(yīng)字符，找到兩者的最長公共
前綴r，并判斷出它們的大小關(guān)系。若r>max_match則令max_match=r,ans=mid。
Step 4 若Suffix(SA[mid])<P 則令left=mid+1，若Suffix(SA[mid])>P 則令
right=mid-1，若Suffix(SA[mid])=P 則轉(zhuǎn)至Step 6。
Step 5 若left<right 則轉(zhuǎn)至Step 2，否則至Step 6。
Step 6 若max_match=m則輸出ans，否則輸出“無匹配”。
注意力很快集中在Step 3，如果能夠避免每次都從頭開始比較Suffix(SA[mid])
和P 的對應(yīng)字符，也許復(fù)雜度就可以進一步降低。
類似于前面求height 數(shù)組，我們考慮利用以前求得的最長公共前綴作為比
較的“基礎(chǔ)”，避免冗余的字符比較。
IOI2004國家集訓(xùn)隊論文 許智磊
第 8 頁 共11頁
在比較Suffix(SA[mid])和P 之前，我們先用常數(shù)時間計算LCP(mid,ans)，
然后比較LCP(mid,ans)和max_match：
情況一：LCP(mid,ans)<max_match，則說明Suffix(SA[mid])和P 的最長公
共前綴就是LCP(mid,ans)，即直接可以確定Step 3 中的r=LCP(mid,ans)，所以
可以直接比較兩者的第r+1 個字符（結(jié)果一定不會是相等）就可以確定
Suffix(SA[mid])和P 的大小。這種情況下，字符比較次數(shù)為1 次。
情況二：LCP(mid,ans)≥max_match，則說明Suffix(SA[mid])和Suffix(SA[ans])
的前max_match個字符一定是相同的，于是Suffix(SA[mid])和P 的前max_match
個字符也是相同的，于是比較兩者的對應(yīng)字符可以從第max_match+1 個開始，
最后求出的r 一定大于等于原先的max_match，字符比較的次數(shù)為rmax_
match+1，不難看出Step 3 執(zhí)行過后max_match將等于r。
設(shè)每次Step 3 執(zhí)行之后max_match 值增加的量為Δmax。在情況一中，
Δmax=0，字符比較次數(shù)為1=Δmax+1；在情況二中，Δmax=r-max_match，字符
比較次數(shù)為r-max_match+1，也是Δmax+1。綜上所述，每次Step 3 進行字符比
較的次數(shù)為Δmax+1。
總共的字符比較次數(shù)為所有的Δmax累加起來再加上Step 3執(zhí)行的次數(shù)。所
有Δmax累加的結(jié)果顯然就是最后的max_match值，不會超過len(P)=m，而Step
3 執(zhí)行的次數(shù)為O(logn)，因此總共的字符比較次數(shù)為O(m+logn)。而整個算法
的復(fù)雜度顯然和字符比較次數(shù)同階，為O(m+logn)。
至此，問題得到圓滿解決，通過O(nlogn)的時間進行預(yù)處理（構(gòu)造后綴數(shù)
組、名詞數(shù)組，計算height 數(shù)組，RMQ 預(yù)處理），之后就可以在O(m+logn)的
時間內(nèi)對一個長度為m 的模式串P 進行模式匹配，這僅僅是在讀入P 的復(fù)雜度
上附加了logn的復(fù)雜度，是非常優(yōu)秀的。
例二 最長回文子串問題
一個回文串是指滿足如下性質(zhì)的字符串u：
u[i]=u[len(u)-i+1]，對所有的1≤i≤len(u)。
也就是說，回文串u 是關(guān)于u 的中間位置“對稱”的。
按照回文串的長度的奇偶性把回文串分為兩類：長度為奇數(shù)的回文串稱為
奇回文串，長度為偶數(shù)的回文串稱為偶回文串。
設(shè)想我們在回文串u 的“中心位置”劃一條直線，顯然，對于奇回文串，
這條線劃在中間一個字符（u[(len(u)+1)/2]）上，而對于偶回文串，這條線劃在
中間的兩個字符（u[len(u)/2]和u[len(u)/2+1]）之間。以下是兩個例子：
回文串里的字符是關(guān)于這條中心線對稱分布的。中心線左邊的字符串顛倒過來
等于右邊的字符串，我們稱之為“反射相等”。
字符串T 的回文子串指的是T 的子串中同時又是回文串的那些字符串。T
的回文子串中長度最大的稱為最長回文子串。類似地定義奇（偶）回文子串和
最長奇（偶）回文子串。
a b c b a c a l f f l a c
IOI2004國家集訓(xùn)隊論文 許智磊
第 9 頁 共11頁
最長回文子串問題是給定一個字符串T，求T 的最長回文子串，簡便起見，
只要求給出最長回文子串的長度即可。
下面我們分析求最長奇回文串的方法，最長偶回文串的求法是類似的。
因為每個奇回文子串一定有一個中心位置（是整個回文串的中間一個字
符），這個中心位置是T 串的某個字符，所以我們首先枚舉定下它的中心位置。
對于一個固定的中心位置i，可能存在多個以T[i]為中心的奇回文子串，但是它
們滿足一個性質(zhì)：奇回文串在T[i]左邊的部分和右邊的部分長度相等，而且關(guān)
于T[i]對稱，即跟T[i]距離相同的左右兩個字符對應(yīng)相等。
那么任何一個以T[i]為中心的奇回文子串都可以表示為T[i-r..i+r],r≥0?？梢?br>看出r 越大這個以T[i]為中心的奇回文串也就越長。因此只要能夠找到最大的
一個r 使得T[i-r..i-1]和T[i+1..i+r]關(guān)于T[i]對稱，也就求出了以T[i]為中心的奇
回文子串中最長的一個（可以看出，也一定只有一個）。如果枚舉i從1 到len(T)，
求出以每個T[i]為中心的奇回文子串中的最長者，這些最長者里面長度最大的
一個也就是整個T串的最長奇回文子串。
如何求以T[i]為中心的奇回文子串中的最長者呢？首先，當(dāng)r=0 時，T[i]單
個字符本身構(gòu)成一個奇回文子串，它的長度為1。下面我們考慮將r 不斷增加，
假設(shè)當(dāng)r=k 時T[i-r..i+r]構(gòu)成奇回文子串，也就是說T[i-r..i-1]和T[i+1..i+r]反射相
等，當(dāng)r=k+1 時，我們比較T[i-(k+1)]與T[i+k+1]這兩個字符，若相等則說明
T[i-(k+1)..i-1]與T[i+1..i+k+1]是關(guān)于T[i]對稱的（因為根據(jù)假設(shè)T[i-k..i-1]與
T[i+1..i+k]已經(jīng)關(guān)于T[i]對稱），于是r可以擴展到k+1。如果T[i-(k+1)]和T[i+k+1]
不同，則說明T[i-(k+1)..i-1]和T[i+1..i+k+1]不對稱，并且對任何r'>k+1，T[i-r'..i-1]
和T[i+1..i+r']也不可能關(guān)于T[i]對稱了，所以r 最大只能到k。
我們把r 遞增的過程稱為向兩邊擴展，擴展一次就可以把以T[i]為中心的
奇回文子串的長度加2。最后r 擴展到的最大值決定了以T[i]為中心的奇回文子
串中的最長者的長度（為2r+1）。
設(shè)len(T)=m，如果用依次比較對應(yīng)字符的方法來求向兩邊擴展的最大值，
則最多可能比較m-1 個字符。由于要枚舉每個位置作為中心向兩邊擴展，所以
最壞情況下總的復(fù)雜度可以達(dá)到O(m2)，不很理想。下面優(yōu)化算法的核心部分
——以一個位置為中心求向兩邊擴展的最大值。
在T 串的末尾添加一個特殊字符'#'，規(guī)定它不等于T 的任何一個字符，然
后把T 串顛倒，接在'#'后，在T'串后再添加特殊字符'$'，規(guī)定它小于前面的任
何一個字符，拼接后形成的串稱為S 串。
不難看出T 串中任何一個字符都可在T'中對稱地找到一個相同的字符。如
果都用S里的字符來表示，S[1..m]是T串，S[m+2..2m+1]是T'串，則每個S[i](1≤i≤m)
關(guān)于'#'對稱的字符是S[2m-i+2]。這樣原先T 串里面的一個子串S[i..j](1≤i≤j≤m)
關(guān)于'#'也可以對稱地找到一個反射相等的子串S[2m-j+2..2m-i+2]。
現(xiàn)在我們定下T 串的某個位置S[i]為中心，假設(shè)向兩邊擴展到了i-r 和i+r，
那么S[i-r..i-1]和S[i+1..i+r]是反射相等的，S[i]可以在T'中找到對稱的字符
S[2m-i+2]，設(shè)i'=2m-i+2，則S[i-r..i-1]也可以在T'中找到對稱的子串S[i'+1..i'+r]，
b a n a n a # a n a n a b $
T T'
i i'=2m-i+2
IOI2004國家集訓(xùn)隊論文 許智磊
第 10 頁 共11頁
那么S[i+1..i+r] 和S[i'+1..i'+r] 同時與S[i-r..i-1]反射相等，也就是說，
S[i+1..i+r]=S[i'+1..i'+r]。又因為S[i]=S[i']，故S[i..i+r]=S[i'..i'+r]。也就是說，
Suffix(i)=r+1Suffix(i')。現(xiàn)在要求r 盡量大，也就是求max{r|Suffix(i)=r+1Suffix(i')}，
不難看出，這里r=LCP(i,i')-1。
上面的推理還存在一個問題，即求出的LCP(i,i')-1 還只能看作r 的一個上
界，還不能當(dāng)成r 的最大值，因為還需要證明給出Suffix(i)和Suffix(i')的最長公
共前綴，一定可以反過來在T 串中找到相應(yīng)的以i 為中心的回文串，這個證明
與前面的推理類似，只是需要注意一點：這里利用到了'#'這個特殊字符避免了
潛在的LCP(i,i')超過實際的r 最大值的危險。這個證明留給讀者自行完成。
總之，我們已經(jīng)確定求以T[i]為中心向兩邊擴展的最大值等價于求
LCP(i,i')，根據(jù)前面后綴數(shù)組和LCP 的相關(guān)內(nèi)容這一步操作可以在常數(shù)時間內(nèi)
完成，只要我們預(yù)先花費O(nlogn)的復(fù)雜度計算后綴數(shù)組、height 數(shù)組和進行
預(yù)處理。其中n=len(S)=2m+2。
現(xiàn)在每次求以一個位置T[i]為中心的回文子串中的最長者的長度可以在常
數(shù)時間內(nèi)完成，我們枚舉i 從1 到m，依次求出所有的這些最長者，記錄其中
最大的一個的長度，就是所要求的最長奇回文子串的長度。由于對每個中心花
費時間為常數(shù)，所以總的復(fù)雜度為O(m)。
因此整個算法的復(fù)雜度是O(nlogn+m)=O(2mlog(2m)+m)=O(mlogm)，是非
常優(yōu)秀的算法，比之前的平方級算法大為改進。
后綴數(shù)組與后綴樹的比較
通過上面的兩個例子相信讀者已經(jīng)對后綴數(shù)組的強大功能有所了解，另一
種數(shù)據(jù)結(jié)構(gòu)——后綴樹，也可以用在這些問題中，那么后綴數(shù)組和后綴樹有什
么區(qū)別和聯(lián)系呢？我們來比較一下：
首先，后綴數(shù)組比較容易理解，也易于編程實現(xiàn)，而且不像后綴樹那樣需
要涉及到指針操作，所以調(diào)試起來比較方便。
第二，后綴數(shù)組占用的空間比后綴樹要小，剛才分析中我們并沒有提到空
間復(fù)雜度的問題，這里簡單說一下：后綴數(shù)組SA 和名詞數(shù)組Rank 都只需要n
個整數(shù)的空間，而在由Rankk計算出SA2k 的過程中需要用兩個一維數(shù)組來輔助
完成，各占n 個整數(shù)的空間，滾動地進行操作，整個算法只需要這四個一維數(shù)
組和常數(shù)個輔助變量，因此總的空間占用為4n個整數(shù)。
而后綴樹通常有2n 個以上節(jié)點，通常每個節(jié)點要兩個整數(shù)（即使采用一些
技巧，至少還是要保存一個整數(shù)），每個節(jié)點要有兩個指針（假設(shè)采用兒子-兄
弟表示方法），因此總共的空間占用至少是4n 個指針和2n 個整數(shù)（至少是n 個
整數(shù)）。如果采用其他方法表示樹狀結(jié)構(gòu)，需要的空間更大。
可以看出后綴數(shù)組的空間需求比后綴樹小。
最后比較它們的復(fù)雜度：
首先按照字符總數(shù)|Σ|把字符集Σ分為三種類型：
若|Σ|是一個常數(shù)，則稱Σ 為Constant Alphabet，
若|Σ|的大小是關(guān)于S 的長度n的多項式函數(shù)，則稱Σ 為Integer Alphabet，
若|Σ|沒有大小上的限制，則稱Σ 為General Alphabet。
IOI2004國家集訓(xùn)隊論文 許智磊
第 11 頁 共11頁
顯然Constant Alphbet 屬于Integer Alphabet 的一種，而Integer Alphabet 是
General Alphabet 的一種。
構(gòu)造后綴數(shù)組的復(fù)雜度與字符集無關(guān)，因為它是直接針對General Alphabet
的算法。
對于普通方法構(gòu)造后綴樹，如果用兒子-兄弟方式表達(dá)樹狀結(jié)構(gòu)，時間復(fù)雜
度達(dá)到O(n*|Σ|)，顯然對于Integer Alphabet 和 General Alphabet 都很低效，對|Σ|
較大的Constant Alphabet 也不適用。
解決的方法是用平衡二叉樹來保存指向兒子的指針，這樣復(fù)雜度變?yōu)?br>O(n*log|Σ|)。
可見后綴樹在某些情況下相對后綴數(shù)組有速度上的優(yōu)勢，但是并不明顯。
對于|Σ|很小的字符串，后綴樹相比后綴數(shù)組的速度優(yōu)勢還是比較可觀的。
尤其是對于很常見的0-1 串。
后綴數(shù)組實際上可以看作后綴樹的所有葉結(jié)點按照從左到右的次序排列放
入數(shù)組中形成的，所以后綴數(shù)組的用途不可能超出后綴樹的范圍。甚至可以說，
如果不配合LCP，后綴數(shù)組的應(yīng)用范圍是很狹窄的。但是LCP 函數(shù)配合下的后
綴數(shù)組就非常強大，可以完成大多數(shù)后綴樹所能完成的任務(wù)，因為LCP 函數(shù)實
際上給出了任意兩個葉子結(jié)點的最近公共祖先，這方面的內(nèi)容大家可以自行研
究。
后綴樹和后綴數(shù)組都是字符串處理中非常優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)，不能說一個肯
定優(yōu)于另一個，對于不同場合、不同條件的問題，我們應(yīng)該靈活應(yīng)用，精心選
擇地選擇其中較為適合的一個。算法和數(shù)據(jù)結(jié)構(gòu)都是死的，而運用它們的人，
才是真正的主角，對經(jīng)典的算法和數(shù)據(jù)結(jié)構(gòu)熟練掌握并適當(dāng)?shù)剡\用以發(fā)揮它們
最大的力量，這才是信息學(xué)研究和競賽中最大的智慧，也是信息學(xué)競賽的魅力
所在。