在字符串處理當(dāng)中，后綴樹(shù)和后綴數(shù)組都是非常有力的工具，其中后綴樹(shù)大家了解得比較多，關(guān)于后綴數(shù)組則很少見(jiàn)于國(guó)內(nèi)的資料。其實(shí)后綴數(shù)組是后綴樹(shù)的一個(gè)非常精巧的替代品，它比后綴樹(shù)容易編程實(shí)現(xiàn)，能夠?qū)崿F(xiàn)后綴樹(shù)的很多功能而時(shí)間復(fù)雜度也不太遜色，并且，它比后綴樹(shù)所占用的空間小很多。可以說(shuō)，在信息學(xué)競(jìng)賽中后綴數(shù)組比后綴樹(shù)要更為實(shí)用。因此在本文中筆者想介紹一下后綴數(shù)組的基本概念、構(gòu)造方法，以及配合后綴數(shù)組的最長(zhǎng)公共前綴數(shù)組的構(gòu)造方法，最后結(jié)合一些例子談?wù)労缶Y數(shù)組的應(yīng)用。


基本概念

首先明確一些必要的定義：

字符集 一個(gè)字符集∑是一個(gè)建立了全序關(guān)系的集合，也就是說(shuō)，∑中的任意兩個(gè)不同的元素α和β都可以比較大小，要么α<β，要么β<α（也就是α>β）。字符集∑中的元素稱(chēng)為字符。
字符串 一個(gè)字符串S是將n個(gè)字符順次排列形成的數(shù)組，n稱(chēng)為S的長(zhǎng)度，表示為len(S)。S的第i個(gè)字符表示為S[i]。
子串 字符串S的子串S[i..j]，i≤j，表示S串中從i到j(luò)這一段，也就是順次排列S[i],S[i+1],...,S[j]形成的字符串。
后綴 后綴是指從某個(gè)位置i開(kāi)始到整個(gè)串末尾結(jié)束的一個(gè)特殊子串。字符串S的從i開(kāi)頭的后綴表示為Suffix(S,i)，也就是Suffix(S,i)=S[i..len(S)]。

關(guān)于字符串的大小比較，是指通常所說(shuō)的“字典順序”比較，也就是對(duì)于兩個(gè)字符串u、v，令i從1開(kā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。
從字符串的大小比較的定義來(lái)看，S的兩個(gè)開(kāi)頭位置不同的后綴u和v進(jìn)行比較的結(jié)果不可能是相等，因?yàn)閡=v的必要條件len(u)=len(v)在這里不可能滿(mǎn)足。

下面我們約定一個(gè)字符集∑和一個(gè)字符串S，設(shè)len(S)=n，且S[n]='$'，也就是說(shuō)S以一個(gè)特殊字符'$'結(jié)尾，并且'$'小于∑中的任何一個(gè)字符。除了S[n]之外，S中的其他字符都屬于∑。對(duì)于約定的字符串S，從位置i開(kāi)頭的后綴直接寫(xiě)成Suffix(i)，省去參數(shù)S。

后綴數(shù)組 后綴數(shù)組SA是一個(gè)一維數(shù)組，它保存1..n的某個(gè)排列SA[1],SA[2],...SA[n]，并且保證 Suffix(SA[i])<Suffix(SA[i+1]),1≤i<n。也就是將S的n個(gè)后綴從小到大進(jìn)行排序之后把排好序的后綴的開(kāi)頭位置順次放入SA中。
名次數(shù)組 名次數(shù)組Rank=SA-1，也就是說(shuō)若SA[i]=j，則Rank[j]=i，不難看出Rank[i]保存的是Suffix(i)在所有后綴中從小到大排列的“名次”。


構(gòu)造方法
如何構(gòu)造后綴數(shù)組呢？最直接最簡(jiǎn)單的方法當(dāng)然是把S的后綴都看作一些普通的字符串，按照一般字符串排序的方法對(duì)它們從小到大進(jìn)行排序。
不難看出，這種做法是很笨拙的，因?yàn)樗鼪](méi)有利用到各個(gè)后綴之間的有機(jī)聯(lián)系，所以它的效率不可能很高。即使采用字符串排序中比較高效的Multi-key Quick Sort，最壞情況的時(shí)間復(fù)雜度仍然是O(n2)的，不能滿(mǎn)足我們的需要。
下面介紹倍增算法(Doubling Algorithm)，它正是充分利用了各個(gè)后綴之間的聯(lián)系，將構(gòu)造后綴數(shù)組的最壞時(shí)間復(fù)雜度成功降至O(nlogn)。

對(duì)一個(gè)字符串u，我們定義u的k-前綴

定義k-前綴比較關(guān)系<k、=k和≤k：
設(shè)兩個(gè)字符串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

直觀地看這些加了一個(gè)下標(biāo)k的比較符號(hào)的意義就是對(duì)兩個(gè)字符串的前k個(gè)字符進(jìn)行字典序比較，特別的一點(diǎn)就是在作大于和小于的比較時(shí)如果某個(gè)字符串的長(zhǎng)度不到k也沒(méi)有關(guān)系，只要能夠在k個(gè)字符比較結(jié)束之前得到第一個(gè)字符串大于或者小于第二個(gè)字符串就可以了。
根據(jù)前綴比較符的性質(zhì)我們可以得到以下的非常重要的性質(zhì)：
性質(zhì)1.1 對(duì)k≥n，Suffix(i)<kSuffix(j) 等價(jià)于 Suffix(i)<Suffix(j)。
性質(zhì)1.2 Suffix(i)=2kSuffix(j)等價(jià)于
Suffix(i)=kSuffix(j) 且 Suffix(i+k)=kSuffix(j+k)。
性質(zhì)1.3 Suffix(i)<2kSuffix(j) 等價(jià)于
Suffix(i)<kS(j) 或 (Suffix(i)=kSuffix(j) 且 Suffix(i+k)<kSuffix(j+k))。
這里有一個(gè)問(wèn)題，當(dāng)i+k>n或者j+k>n的時(shí)候Suffix(i+k)或Suffix(j+k)是無(wú)明確定義的表達(dá)式，但實(shí)際上不需要考慮這個(gè)問(wèn)題，因?yàn)榇藭r(shí)Suffix(i)或者Suffix(j)的長(zhǎng)度不超過(guò)k，也就是說(shuō)它們的k-前綴以'$'結(jié)尾，于是k-前綴比較的結(jié)果不可能相等，也就是說(shuō)前k個(gè)字符已經(jīng)能夠比出大小，后面的表達(dá)式自然可以忽略，這也就看出我們規(guī)定S以'$'結(jié)尾的特殊用處了。

定義k-后綴數(shù)組 SAk保存1..n的某個(gè)排列SAk[1],SAk[2],…SAk[n]使得Suffix(SAk[i]) ≤kSuffix(SAk[i+1]),1≤i<n。也就是說(shuō)對(duì)所有的后綴在k-前綴比較關(guān)系下從小到大排序，并且把排序后的后綴的開(kāi)頭位置順次放入數(shù)組SAk中。
定義k-名次數(shù)組Rankk，Rankk[i]代表Suffix(i)在k-前綴關(guān)系下從小到大的“名次”，也就是1加上滿(mǎn)足Suffix(j)<kSuffix(i)的j的個(gè)數(shù)。通過(guò)SAk很容易在O(n)的時(shí)間內(nèi)求出Rankk。
假設(shè)我們已經(jīng)求出了SAk和Rankk，那么我們可以很方便地求出SA2k和Rank2k，因?yàn)楦鶕?jù)性質(zhì)1.2和1.3，2k-前綴比較關(guān)系可以由常數(shù)個(gè)k -前綴比較關(guān)系組合起來(lái)等價(jià)地表達(dá)，而Rankk數(shù)組實(shí)際上給出了在常數(shù)時(shí)間內(nèi)進(jìn)行<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ù)時(shí)間內(nèi)完成，于是對(duì)所有的后綴在≤k關(guān)系下進(jìn)行排序也就和一般的排序沒(méi)有什么區(qū)別了，它實(shí)際上就相當(dāng)于每個(gè)Suffix(i)有一個(gè)主關(guān)鍵字Rankk[i]和一個(gè)次關(guān)鍵字Rankk[i+k]。如果采用快速排序之類(lèi)O (nlogn)的排序，那么從SAk和Rankk構(gòu)造出SA2k的復(fù)雜度就是O(nlogn)。更聰明的方法是采用基數(shù)排序，復(fù)雜度為O(n)。
求出SA2k之后就可以在O(n)的時(shí)間內(nèi)根據(jù)SA2k構(gòu)造出Rank2k。因此，從SAk和Rankk推出SA2k和Rank2k可以在O(n)時(shí)間內(nèi)完成。
下面只有一個(gè)問(wèn)題需要解決：如何構(gòu)造出SA1和Rank1。這個(gè)問(wèn)題非常簡(jiǎn)單：因?yàn)?lt;1，=1和≤1這些運(yùn)算符實(shí)際上就是對(duì)字符串的第一個(gè)字符進(jìn)行比較，所以只要把每個(gè)后綴按照它的第一個(gè)字符進(jìn)行排序就可以求出SA1，不妨就采用快速排序，復(fù)雜度為O(nlogn)。
于是，可以在O(nlogn)的時(shí)間內(nèi)求出SA1和Rank1。
求出了SA1和Rank1，我們可以在O(n)的時(shí)間內(nèi)求出SA2和Rank2，同樣，我們可以再用O(n)的時(shí)間求出SA4和Rank4，這樣，我們依次求出：
SA2和Rank2，SA4和Rank4，SA8和Rank8，……直到SAm和Rankm，其中m=2k且m≥n。而根據(jù)性質(zhì)1.1，SAm和SA是等價(jià)的。這樣一共需要進(jìn)行l(wèi)ogn次O(n)的過(guò)程，因此
可以在O(nlogn)的時(shí)間內(nèi)計(jì)算出后綴數(shù)組SA和名次數(shù)組Rank。

最長(zhǎng)公共前綴
現(xiàn)在一個(gè)字符串S的后綴數(shù)組SA可以在O(nlogn)的時(shí)間內(nèi)計(jì)算出來(lái)。利用SA我們已經(jīng)可以做很多事情，比如在O(mlogn)的時(shí)間內(nèi)進(jìn)行模式匹配，其中m,n分別為模式串和待匹配串的長(zhǎng)度。但是要想更充分地發(fā)揮后綴數(shù)組的威力，我們還需要計(jì)算一個(gè)輔助的工具——最長(zhǎng)公共前綴（Longest Common Prefix）。
對(duì)兩個(gè)字符串u,v定義函數(shù)lcp(u,v)=max{i|u=iv}，也就是從頭開(kāi)始順次比較u和v的對(duì)應(yīng)字符，對(duì)應(yīng)字符持續(xù)相等的最大位置，稱(chēng)為這兩個(gè)字符串的最長(zhǎng)公共前綴。
對(duì)正整數(shù)i,j定義LCP(i,j)=lcp(Suffix(SA[i]),Suffix(SA[j])，其中i,j均為1至n的整數(shù)。LCP(i,j)也就是后綴數(shù)組中第i個(gè)和第j個(gè)后綴的最長(zhǎng)公共前綴的長(zhǎng)度。
關(guān)于LCP有兩個(gè)顯而易見(jiàn)的性質(zhì)：
性質(zhì)2.1 LCP(i,j)=LCP(j,i)
性質(zhì)2.2 LCP(i,i)=len(Suffix(SA[i]))=n-SA[i]+1
這兩個(gè)性質(zhì)的用處在于，我們計(jì)算LCP(i,j)時(shí)只需要考慮i<j的情況，因?yàn)閕>j時(shí)可交換i,j，i=j時(shí)可以直接輸出結(jié)果n-SA[i]+1。

直接根據(jù)定義，用順次比較對(duì)應(yīng)字符的方法來(lái)計(jì)算LCP(i,j)顯然是很低效的，時(shí)間復(fù)雜度為O(n)，所以我們必須進(jìn)行適當(dāng)?shù)念A(yù)處理以降低每次計(jì)算LCP的復(fù)雜度。
經(jīng)過(guò)仔細(xì)分析，我們發(fā)現(xiàn)LCP函數(shù)有一個(gè)非常好的性質(zhì)：
設(shè)i<j，則LCP(i,j)=min{LCP(k-1,k)|i+1≤k≤j} （LCP Theorem）

要證明LCP Theorem，首先證明LCP Lemma:
對(duì)任意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。
設(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說(shuō)明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í)，顯然成立。
設(shè)j-i=m時(shí)LCP Theorem成立，當(dāng)j-i=m+1時(shí)，
由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時(shí)，仍有
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得出必然的一個(gè)推論：
LCP Corollary 對(duì)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}，也就是說(shuō)，計(jì)算LCP(i,j)等同于詢(xún)問(wèn)一維數(shù)組height中下標(biāo)在i+1到j(luò)范圍內(nèi)的所有元素的最小值。如果height數(shù)組是固定的，這就是非常經(jīng)典的RMQ（Range Minimum Query）問(wèn)題。
RMQ問(wèn)題可以用線段樹(shù)或靜態(tài)排序樹(shù)在O(nlogn)時(shí)間內(nèi)進(jìn)行預(yù)處理，之后每次詢(xún)問(wèn)花費(fèi)時(shí)間O(logn)，更好的方法是RMQ標(biāo)準(zhǔn)算法，可以在O(n)時(shí)間內(nèi)進(jìn)行預(yù)處理，每次詢(xún)問(wèn)可以在常數(shù)時(shí)間內(nèi)完成。
對(duì)于一個(gè)固定的字符串S，其height數(shù)組顯然是固定的，只要我們能高效地求出height數(shù)組，那么運(yùn)用RMQ方法進(jìn)行預(yù)處理之后，每次計(jì)算LCP(i,j)的時(shí)間復(fù)雜度就是常數(shù)級(jí)了。于是只有一個(gè)問(wèn)題——如何盡量高效地算出height數(shù)組。
根據(jù)計(jì)算后綴數(shù)組的經(jīng)驗(yàn)，我們不應(yīng)該把n個(gè)后綴看作互不相關(guān)的普通字符串，而應(yīng)該盡量利用它們之間的聯(lián)系，下面證明一個(gè)非常有用的性質(zhì)：
為了描述方便，設(shè)h[i]=height[Rank[i]]，即height[i]=h[SA[i]]。h數(shù)組滿(mǎn)足一個(gè)性質(zhì)：
性質(zhì)3 對(duì)于i>1且Rank[i]>1，一定有h[i]≥h[i-1]-1。
為了證明性質(zhì)3，我們有必要明確兩個(gè)事實(shí)：

設(shè)i<n,j<n，Suffix(i)和Suffix(j)滿(mǎn)足lcp(Suffix(i),Suffix(j)>1，則成立以下兩點(diǎn)：
Fact 1 Suffix(i)<Suffix(j) 等價(jià)于 Suffix(i+1)<Suffix(j+1)。
Fact 2 一定有l(wèi)cp(Suffix(i+1),Suffix(j+1))=lcp(Suffix(i),Suffix(j))-1。
看起來(lái)很神奇，但其實(shí)很自然：lcp(Suffix(i),Suffix(j))>1說(shuō)明Suffix(i)和Suffix(j)的第一個(gè)字符是相同的，設(shè)它為α，則Suffix(i)相當(dāng)于α后連接Suffix(i+1)，Suffix(j)相當(dāng)于α后連接Suffix(j+1)。比較Suffix (i)和Suffix(j)時(shí)，第一個(gè)字符α是一定相等的，于是后面就等價(jià)于比較Suffix(i)和Suffix(j)，因此Fact 1成立。Fact 2可類(lèi)似證明。

于是可以證明性質(zhì)3：
當(dāng)h[i-1]≤1時(shí)，結(jié)論顯然成立，因h[i]≥0≥h[i-1]-1。
當(dāng)h[i-1]>1時(shí)，也即height[Rank[i-1]]>1，可見(jiàn)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)從第一個(gè)字符開(kāi)始依次比較直到有字符不相同，由此計(jì)算出h[i]。字符比較次數(shù)為h[i]+1，不超過(guò)h[i]-h[i-1]+2。
否則，說(shuō)明i>1，Rank[i]>1，h[i-1]>1，根據(jù)性質(zhì)3，Suffix(i)和Suffix(Rank[i]-1)至少有前h[i-1]-1個(gè)字符是相同的，于是字符比較可以從h[i-1]開(kāi)始，直到某個(gè)字符不相同，由此計(jì)算出h[i]。字符比較次數(shù)為h[i]-h[i- 1]+2。

設(shè)SA[1]=p，那么不難看出總的字符比較次數(shù)不超過(guò)

也就是說(shuō)，整個(gè)算法的復(fù)雜度為O(n)。
求出了h數(shù)組，根據(jù)關(guān)系式height[i]=h[SA[i]]可以在O(n)時(shí)間內(nèi)求出height數(shù)組，于是
可以在O(n)時(shí)間內(nèi)求出height數(shù)組。

結(jié)合RMQ方法，在O(n)時(shí)間和空間進(jìn)行預(yù)處理之后就能做到在常數(shù)時(shí)間內(nèi)計(jì)算出對(duì)任意(i,j)計(jì)算出LCP(i,j)。
因?yàn)閘cp(Suffix(i),Suffix(j))=LCP(Rank[i],Rank[j])，所以我們也就可以在常數(shù)時(shí)間內(nèi)求出S的任何兩個(gè)后綴之間的最長(zhǎng)公共前綴。這正是后綴數(shù)組能強(qiáng)有力地處理很多字符串問(wèn)題的重要原因之一。
后綴數(shù)組的應(yīng)用
下面結(jié)合兩個(gè)例子談?wù)勅绾芜\(yùn)用后綴數(shù)組.

例一 多模式串的模式匹配問(wèn)題
給定一個(gè)固定待匹配串S,長(zhǎng)度為n,然后每次輸入一個(gè)模式串P,長(zhǎng)度為m,要求返回P在S中的一個(gè)匹配或者返回匹配失敗.所謂匹配指某個(gè)位置i滿(mǎn)足1≤i≤n-m+1使得S[i..(i+m-1)]=P,也即Suffix(i)=mP.
我們知道,如果只有一個(gè)模式串,最好的算法就是KMP算法,時(shí)間復(fù)雜度為O(n+m),但是如果有多個(gè)模式串,我們就要考慮做適當(dāng)?shù)念A(yù)處理使得對(duì)每個(gè)模式串進(jìn)行匹配所花的時(shí)間小一些.最簡(jiǎn)單的預(yù)處理莫過(guò)于建立S的后綴數(shù)組(先在S的后面添加'$'),然后每次尋找匹配轉(zhuǎn)化為用二分查找法在SA中找到和P的公共前綴最長(zhǎng)的一個(gè)后綴,判斷這個(gè)最長(zhǎng)的公共前綴是否等于m.這樣,每次比較P和一個(gè)后綴的復(fù)雜度為O(m),因?yàn)樽顗那闆r下可能比較了m個(gè)字符.二分查找需要調(diào)用比較的次數(shù)為O(logn),因此總復(fù)雜度為O(mlogn),于是每次匹配的復(fù)雜度從O(n+m)變?yōu)镺(mlogn),可以說(shuō)改進(jìn)了不少.可是這樣仍然不能令我們滿(mǎn)足.前面提到LCP可以增加后綴數(shù)組的威力,

我們來(lái)試試用在這個(gè)問(wèn)題上.
我們分析原始的二分查找算法,大體有以下幾步:
Step 1 令left=1,right=n,max_match=0.
Step 2 令mid=(left+right)/2(這里"/"表示取整除法).
Step 3 順次比較Suffix(SA[mid])和P的對(duì)應(yīng)字符,找到兩者的最長(zhǎng)公共
前綴r,并判斷出它們的大小關(guān)系.若r>max_match則令max_match=r,ans=mid.
Step 4 若Suffix(SA[mid])P則令
right=mid-1,若Suffix(SA[mid])=P則轉(zhuǎn)至Step 6.
Step 5 若left
Step 6 若max_match=m則輸出ans,否則輸出"無(wú)匹配".
注意力很快集中在Step 3,如果能夠避免每次都從頭開(kāi)始比較Suffix(SA[mid])和P的對(duì)應(yīng)字符,也許復(fù)雜度就可以進(jìn)一步降低.類(lèi)似于前面求height數(shù)組,我們考慮利用以前求得的最長(zhǎng)公共前綴作為比較的"基礎(chǔ)",避免冗余的字符比較.

在比較Suffix(SA[mid])和P之前,我們先用常數(shù)時(shí)間計(jì)算LCP(mid,ans),然后比較LCP(mid,ans)和max_match:情況一:LCP(mid,ans)k+1,T[i-r'..i-1]和T[i+1..i+r']也不可能關(guān)于T[i]對(duì)稱(chēng)了,所以r最大只能到k.我們把r遞增的過(guò)程稱(chēng)為向兩邊擴(kuò)展,擴(kuò)展一次就可以把以T[i]為中心的奇回文子串的長(zhǎng)度加2.最后r擴(kuò)展到的最大值決定了以T[i]為中心的奇回文子串中的最長(zhǎng)者的長(zhǎng)度(為2r+1).設(shè)len(T)=m,如果用依次比較對(duì)應(yīng)字符的方法來(lái)求向兩邊擴(kuò)展的最大值,則最多可能比較m-1個(gè)字符.由于要枚舉每個(gè)位置作為中心向兩邊擴(kuò)展,所以最壞情況下總的復(fù)雜度可以達(dá)到O(m2),不很理想.
下面優(yōu)化算法的核心部分
——以一個(gè)位置為中心求向兩邊擴(kuò)展的最大值.
在T串的末尾添加一個(gè)特殊字符'#',規(guī)定它不等于T的任何一個(gè)字符,然后把T串顛倒,接在'#'后,在T'串后再添加特殊字符'$',規(guī)定它小于前面的任何一個(gè)字符,拼接后形成的串稱(chēng)為S串.不難看出T串中任何一個(gè)字符都可在T'中對(duì)稱(chēng)地找到一個(gè)相同的字符.如果都用S里的字符來(lái)表示,S[1..m]是T串,S[m+2..2m+1]是T'串,則每個(gè)S[i](1≤i≤m)關(guān)于'#'對(duì)稱(chēng)的字符是S[2m-i+2].這樣原先T串里面的一個(gè)子串S[i..j](1≤i≤j≤m)關(guān)于'#'也可以對(duì)稱(chēng)地找到一個(gè)反射相等的子串S[2m-j+2..2m-i+2].
現(xiàn)在我們定下T串的某個(gè)位置S[i]為中心,假設(shè)向兩邊擴(kuò)展到了i-r和i+r,那么S[i-r..i-1]和S[i+1..i+r]是反射相等的,S[i]可以在T'中找到對(duì)稱(chēng)的字符S[2m-i+2],設(shè)i'=2m-i+2,則S[i-r..i-1]也可以在T'中找到對(duì)稱(chēng)的子串S[i'+1..i'+r],
banana#ananab$
TT'
ii'=2m-i+2
那么S[i+1..i+r]和S[i'+1..i'+r]同時(shí)與S[i-r..i-1]反射相等,也就是說(shuō),S[i+1..i+r]=S[i'+1..i'+r].又因?yàn)镾[i]=S[i'],故S[i..i+r]=S[i'..i'+r].也就是說(shuō),Suffix(i)=r+1Suffix(i').現(xiàn)在要求r盡量大,也就是求max{r|Suffix(i)=r+1Suffix(i')},不難看出,這里r=LCP(i,i')-1.上面的推理還存在一個(gè)問(wèn)題,即求出的LCP(i,i')-1還只能看作r的一個(gè)上界,還不能當(dāng)成r的最大值,因?yàn)檫€需要證明給出Suffix(i)和Suffix(i')的最長(zhǎng)公共前綴,一定可以反過(guò)來(lái)在T串中找到相應(yīng)的以i為中心的回文串,這個(gè)證明與前面的推理類(lèi)似,只是需要注意一點(diǎn):這里利用到了'#'這個(gè)特殊字符避免了潛在的LCP(i,i')超過(guò)實(shí)際的r最大值的危險(xiǎn).這個(gè)證明留給讀者自行完成.總之,我們已經(jīng)確定求以T[i]為中心向兩邊擴(kuò)展的最大值等價(jià)于求LCP(i,i'),根據(jù)前面后綴數(shù)組和LCP的相關(guān)內(nèi)容這一步操作可以在常數(shù)時(shí)間內(nèi)完成,只要我們預(yù)先花費(fèi)O(nlogn)的復(fù)雜度計(jì)算后綴數(shù)組,height數(shù)組和進(jìn)行預(yù)處理.其中n=len(S)=2m+2.
現(xiàn)在每次求以一個(gè)位置T[i]為中心的回文子串中的最長(zhǎng)者的長(zhǎng)度可以在常數(shù)時(shí)間內(nèi)完成,我們枚舉i從1到m,依次求出所有的這些最長(zhǎng)者,記錄其中最大的一個(gè)的長(zhǎng)度,就是所要求的最長(zhǎng)奇回文子串的長(zhǎng)度.由于對(duì)每個(gè)中心花費(fèi)時(shí)間為常數(shù),所以總的復(fù)雜度為O(m).因此整個(gè)算法的復(fù)雜度是O(nlogn+m)=O(2mlog(2m)+m)=O(mlogm),是非常優(yōu)秀的算法,比之前的平方級(jí)算法大為改進(jìn).

后綴數(shù)組與后綴樹(shù)的比較
通過(guò)上面的兩個(gè)例子相信讀者已經(jīng)對(duì)后綴數(shù)組的強(qiáng)大功能有所了解,另一種數(shù)據(jù)結(jié)構(gòu)——后綴樹(shù),也可以用在這些問(wèn)題中,那么后綴數(shù)組和后綴樹(shù)有什么區(qū)別和聯(lián)系呢 我們來(lái)比較一下:
首先,后綴數(shù)組比較容易理解,也易于編程實(shí)現(xiàn),而且不像后綴樹(shù)那樣需要涉及到指針操作,所以調(diào)試起來(lái)比較方便.第二,后綴數(shù)組占用的空間比后綴樹(shù)要小,剛才分析中我們并沒(méi)有提到空間復(fù)雜度的問(wèn)題,這里簡(jiǎn)單說(shuō)一下:后綴數(shù)組SA和名詞數(shù)組Rank都只需要n個(gè)整數(shù)的空間,而在由Rankk計(jì)算出SA2k的過(guò)程中需要用兩個(gè)一維數(shù)組來(lái)輔助完成,各占n個(gè)整數(shù)的空間,滾動(dòng)地進(jìn)行操作,整個(gè)算法只需要這四個(gè)一維數(shù)組和常數(shù)個(gè)輔助變量,因此總的空間占用為4n個(gè)整數(shù).而后綴樹(shù)通常有2n個(gè)以上節(jié)點(diǎn),通常每個(gè)節(jié)點(diǎn)要兩個(gè)整數(shù)(即使采用一些技巧,至少還是要保存一個(gè)整數(shù)),每個(gè)節(jié)點(diǎn)要有兩個(gè)指針(假設(shè)采用兒子-兄弟表示方法),因此總共的空間占用至少是4n個(gè)指針和2n個(gè)整數(shù)(至少是n個(gè)整數(shù)).如果采用其他方法表示樹(shù)狀結(jié)構(gòu),需要的空間更大.可以看出后綴數(shù)組的空間需求比后綴樹(shù)小.
最后比較它們的復(fù)雜度:
首先按照字符總數(shù)|∑|把字符集∑分為三種類(lèi)型:
若|∑|是一個(gè)常數(shù),則稱(chēng)∑為Constant Alphabet,
若|∑|的大小是關(guān)于S的長(zhǎng)度n的多項(xiàng)式函數(shù),則稱(chēng)∑為Integer Alphabet,
若|∑|沒(méi)有大小上的限制,則稱(chēng)∑為General Alphabet.

顯然Constant Alphbet屬于Integer Alphabet的一種,而Integer Alphabet是General Alphabet的一種.構(gòu)造后綴數(shù)組的復(fù)雜度與字符集無(wú)關(guān),因?yàn)樗侵苯俞槍?duì)General Alphabet的算法.對(duì)于普通方法構(gòu)造后綴樹(shù),如果用兒子-兄弟方式表達(dá)樹(shù)狀結(jié)構(gòu),時(shí)間復(fù)雜度達(dá)到O(n*|∑|),顯然對(duì)于Integer Alphabet 和 General Alphabet都很低效,對(duì)|∑|較大的Constant Alphabet也不適用.解決的方法是用平衡二叉樹(shù)來(lái)保存指向兒子的指針,這樣復(fù)雜度變?yōu)镺(n*log|∑|).可見(jiàn)后綴樹(shù)在某些情況下相對(duì)后綴數(shù)組有速度上的優(yōu)勢(shì),但是并不明顯.對(duì)于|∑|很小的字符串,后綴樹(shù)相比后綴數(shù)組的速度優(yōu)勢(shì)還是比較可觀的.尤其是對(duì)于很常見(jiàn)的0-1串.
后綴數(shù)組實(shí)際上可以看作后綴樹(shù)的所有葉結(jié)點(diǎn)按照從左到右的次序排列放入數(shù)組中形成的,所以后綴數(shù)組的用途不可能超出后綴樹(shù)的范圍.甚至可以說(shuō),如果不配合LCP,后綴數(shù)組的應(yīng)用范圍是很狹窄的.但是LCP函數(shù)配合下的后綴數(shù)組就非常強(qiáng)大,可以完成大多數(shù)后綴樹(shù)所能完成的任務(wù),因?yàn)長(zhǎng)CP函數(shù)實(shí)際上給出了任意兩個(gè)葉子結(jié)點(diǎn)的最近公共祖先,這方面的內(nèi)容大家可以自行研
究.后綴樹(shù)和后綴數(shù)組都是字符串處理中非常優(yōu)秀的數(shù)據(jù)結(jié)構(gòu),不能說(shuō)一個(gè)肯定優(yōu)于另一個(gè),對(duì)于不同場(chǎng)合,不同條件的問(wèn)題,我們應(yīng)該靈活應(yīng)用,精心選擇地選擇其中較為適合的一個(gè).算法和數(shù)據(jù)結(jié)構(gòu)都是死的,而運(yùn)用它們的人,才是真正的主角,對(duì)經(jīng)典的算法和數(shù)據(jù)結(jié)構(gòu)熟練掌握并適當(dāng)?shù)剡\(yùn)用以發(fā)揮它們最大的力量,這才是信息學(xué)研究和競(jìng)賽中最大的智慧,也是信息學(xué)競(jìng)賽的魅力
所在.