2011年軟考程序員考試復習筆試知識點整理(16)

　　(2)后綴數(shù)組的應(yīng)用--height數(shù)組

　　在介紹后綴數(shù)組的應(yīng)用前，先介紹后綴數(shù)組的一個重要附屬數(shù)組：height數(shù)組。

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

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

　　這里給出代碼：

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

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

　　(3) 后綴數(shù)組解題總結(jié)

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

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

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

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

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

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

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

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

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

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

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

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

　　6、最長回文子串 ural1297

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

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

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

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

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