在字符串處理當中，后綴樹和后綴數組都是非常有力的工具，其中后綴樹大家了解得比較多，關于后綴數組則很少見于國內的資料。其實后綴數組是后綴樹的一個非常精巧的替代品，它比后綴樹容易編程實現，能夠實現后綴樹的很多功能而時間復雜度也不太遜色，并且，它比后綴樹所占用的空間小很多?？梢哉f，在信息學競賽中后綴數組比后綴樹要更為實用。因此在本文中筆者想介紹一下后綴數組的基本概念、構造方法，以及配合后綴數組的最長公共前綴數組的構造方法，最后結合一些例子談談后綴數組的應用。


基本概念

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

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

關于字符串的大小比較，是指通常所說的“字典順序”比較，也就是對于兩個字符串u、v，令i從1開始順次比較u[i]和v[i]，如果相等則令i加1，否則若u[i]<v[i]則認為u<v，u[i]>v[i]則認為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[i])<Suffix(SA[i+1]),1≤i<n。也就是將S的n個后綴從小到大進行排序之后把排好序的后綴的開頭位置順次放入SA中。
名次數組 名次數組Rank=SA-1，也就是說若SA[i]=j，則Rank[j]=i，不難看出Rank[i]保存的是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[i]) ≤kSuffix(SAk[i+1]),1≤i<n。也就是說對所有的后綴在k-前綴比較關系下從小到大排序，并且把排序后的后綴的開頭位置順次放入數組SAk中。
定義k-名次數組Rankk，Rankk[i]代表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[i]<Rankk[j]
Suffix(i)=kSuffix(j) 當且僅當 Rankk[i]=Rankk[j]
因此，比較Suffix(i)和Suffix(j)在k-前綴比較關系下的大小可以在常數時間內完成，于是對所有的后綴在≤k關系下進行排序也就和一般的排序沒有什么區別了，它實際上就相當于每個Suffix(i)有一個主關鍵字Rankk[i]和一個次關鍵字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[i]),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[i]))=n-SA[i]+1
這兩個性質的用處在于，我們計算LCP(i,j)時只需要考慮i<j的情況，因為i>j時可交換i,j，i=j時可以直接輸出結果n-SA[i]+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[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)

又設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[i]=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[i]=height[Rank[i]]，即height[i]=h[SA[i]]。h數組滿足一個性質：
性質3 對于i>1且Rank[i]>1，一定有h[i]≥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[i]≥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[i]，也就是Rank[k+1]≤Rank[i]-1。
于是根據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。

根據性質3，可以令i從1循環到n按照如下方法依次算出h[i]：
若Rank[i]=1，則h[i]=0。字符比較次數為0。
若i=1或者h[i-1]≤1，則直接將Suffix(i)和Suffix(Rank[i]-1)從第一個字符開始依次比較直到有字符不相同，由此計算出h[i]。字符比較次數為h[i]+1，不超過h[i]-h[i-1]+2。
否則，說明i>1，Rank[i]>1，h[i-1]>1，根據性質3，Suffix(i)和Suffix(Rank[i]-1)至少有前h[i-1]-1個字符是相同的，于是字符比較可以從h[i-1]開始，直到某個字符不相同，由此計算出h[i]。字符比較次數為h[i]-h[i- 1]+2。

設SA[1]=p，那么不難看出總的字符比較次數不超過

也就是說，整個算法的復雜度為O(n)。
求出了h數組，根據關系式height[i]=h[SA[i]]可以在O(n)時間內求出height數組，于是
可以在O(n)時間內求出height數組。

結合RMQ方法，在O(n)時間和空間進行預處理之后就能做到在常數時間內計算出對任意(i,j)計算出LCP(i,j)。
因為lcp(Suffix(i),Suffix(j))=LCP(Rank[i],Rank[j])，所以我們也就可以在常數時間內求出S的任何兩個后綴之間的最長公共前綴。這正是后綴數組能強有力地處理很多字符串問題的重要原因之一。
后綴數組的應用
下面結合兩個例子談談如何運用后綴數組.

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

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

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

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

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