(2)后綴數組的應用--height數組

　　在介紹后綴數組的應用前，先介紹后綴數組的一個重要附屬數組：height數組。

　　1、height 數組：定義height[i]=suffix(sa[i-1])和suffix(sa[i])的最長公共前綴，也就是排名相鄰的兩個后綴的最長公共前綴。height數組是應用后綴數組解題是的核心，基本上使用后綴數組解決的題目都是依賴height數組完成的。

　　2、height數組的求法：具體的求法參見羅穗騫的論文。對于height數組的求法，我并沒有去深刻理解，單純地記憶了而已...有興趣的朋友可以去鉆研鉆研再和我交流交流

　　這里給出代碼：

　　intrank[maxn],height[maxn];

　　void calheight(int*r,int *sa,int n)

　　{

　　int i,j,k=0;

　　for(i=1;i<=n;i++) rank[sa[i]]=i;

　　for(i=0;i

　　for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);

　　return;

　　}

　　3、一些注意事項：height數組的值應該是從height[1]開始的，而且height[1]應該是等于0的。原因是，因為我們在字符串后面添加了一個0號字符，所以它必然是最小的一個后綴。而字符串中的其他字符都應該是大于0的(前面有提到，使用倍增算法前需要確保這點)，所以排名第二的字符串和0號字符的公共前綴(即height[1])應當為0.在調用calheight函數時，要注意height數組的范圍應該是[1..n]。所以調用時應該是calheight(r,sa,n)而不是calheight(r,sa,n+1)。要理解清楚這里的n的含義是什么。

　　calheight過程中，對rank數組求值的for語句的初始語句是i=1而不是i=0的原因，和上面說的類似，因為sa[0]總是等于那個已經失去作用的0號字符，所以沒必要求出其rank值。當然你錯寫成for (i=0..)，也不會有什么問題。

　　(3) 后綴數組解題總結

　　1、求單個子串的不重復子串個數。SPOJ 694、SPOJ 705.

　　這個問題是一個特殊求值問題。要認識到這樣一個事實：一個字符串中的所有子串都必然是它的后綴的前綴。(這句話稍微有點繞...)對于每一個sa[i]后綴，它的起始位置sa[i]，那么它最多能得到該后綴長度個子串(n-sa[i]個)，而其中有height[i]個是與前一個后綴相同的，所以它能產生的實際后綴個數便是n-sa[i]-height[i]。遍歷一次所有的后綴，將它產生的后綴數加起來便是答案。

　　2、后綴的最長公共前綴。(記為lcp(x，y))

　　這是height數組的最基本性質之一。具體的可以參看羅穗騫的論文。后綴i和后綴j的最長公共前綴的長度為它們在sa數組中所在排位之間的height值中的最小值。這個描述可能有點亂，正規的說，令x=rank[i],y=rank[j]，x

　　3、最長重復子串(可重疊)

　　要看到，任何一個重復子串，都必然是某兩個后綴的最長公共前綴。因為，兩個后綴的公共前綴，它出現在這兩個后綴中，并且起始位置時不同的，所以這個公共前綴必然重復出現兩次以上(可重疊)。而任何兩個后綴的最長公共前綴為某一段height值中的最小值，所以最大為height值中的最大值(即某個lcp(sa[i],sa[i+1]))。所以只要算出height數組，然后輸出最大值就可以了。

　　4、最長重復不重疊子串 PKU1743

　　這個問題和3的唯一區別在于能否重疊。加上不能重疊這個限制后，直接求解比較困難，所以我們選擇二分枚舉答案，將問題轉換為判定性問題。假設當時枚舉的長度為k，那么要怎樣判斷是否存在長度為k的重復不重疊子串呢?

　　首先，根據height數組，將后綴分成若干組，使得每組后綴中，后綴之間的height值不小于k。這樣分組之后，不難看出，如果某組后綴數量大于1，那么它們之中存在一個公共前綴，其長度為它們之間的height值的最小值。而我們分組之后，每組后綴之間height值的最小值大于等于k。所以，后綴數大于1的分組中，有可能存在滿足題目限制條件的長度不小于k的子串。只要判斷滿足題目限制條件成立，那么說明存在長度至少為k的合法子串。

　　對于本題，限制條件是不重疊，判斷的方法是，一組后綴中，起始位置最大的后綴的起始位置減去起始位置最小的后綴的起始位置>=k。滿足這個條件的話，那么這兩個后綴的公共前綴不但出現兩次，而且出現兩次的起始位置間隔大于等于k，所以不會重疊。

　　5、最長的出現k次的重復(可重疊)子串。 PKU3261

　　使用后綴數組解題時，遇到“最長”，除了特殊情況外(如問題3)，一般需要二分答案，利用height值進行分組。本題的限制條件為出現k次。只需判斷，有沒有哪一組后綴數量不少于k就可以了。相信有了我前面問題的分析作為基礎，這個應該不難理解。注意理解“不少于k次”而不是“等于k次”的原因。如果理解不了，可以找個具體的例子來分析分析。

　　6、最長回文子串 ural1297

　　這個問題沒有很直接的方法可以解決，但可以采用枚舉的方法。具體的就是枚舉回文子串的中心所在位置i。注意要分回文子串的長度為奇數還是偶數兩種情況分析。然后，我們要做的，是要求出以i為中心的回文子串最長為多長。利用后綴數組，可以設計出這樣一種求法：求i往后的后綴與i往前的前綴的最長公共前綴。我這里的表述有些問題，不過不影響理解。

　　要快速地求這個最長前綴，可以將原串反寫之后接在原串后面。在使用后綴數組的題目中，連接兩個(n個)字符串時，中間要用不可能會出現在原串中，不一樣的非0號的字符將它們隔開。這樣可以做到不影響后綴數組的性質。然后，問題就可以轉化為求兩個后綴的最長公共前綴了。具體的細節，留給大家自己思考...(懶...原諒我吧，都打這么多字了..一個多小時了啊TOT)

　　軟考程序員考試歷年真題重點題總結及答案

　　2011年上半年軟考報名時間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)