後綴數組總結(註：僅供自己參考)

後綴數組總結 - CSDN博客?

blog.csdn.net

後綴數組——處理字元串的有力工具 作者：羅穗騫 ２００９年１月 　　【摘要】 　　後綴數組是處理字元串的有力工具。後綴數組是後綴樹的一個非常精巧的替代品，它比後綴樹容易編程實現，能夠實現後綴樹的很多功能而時間複雜度也並不遜色，而且它比後綴樹所佔用的內存空間小很多。可以說，在信息學競賽中後綴數組比後綴樹要更為實用。本文分兩部分。第一部分介紹兩種構造後綴數組的方法，重點介紹如何用簡潔高效的代碼實現，並對兩種演算法進行了比較。第二部分介紹後綴數組在各種類型題目中的具體應用。 　　【關鍵字】 　　字元串，後綴，後綴數組，名次數組，基數排序， 　　【正文】 一、後綴數組的實現 　　本節主要介紹後綴數組的兩種實現方法：倍增演算法（Doubling Algorithm）和DC3演算法（Difference Cover），並對兩種演算法進行了比較。可能有的讀者會認為這兩種演算法難以理解，即使理解了也難以用程序實現。本節針對這個問題，在介紹這兩種演算法的基礎上，還給出了簡潔高效的代碼。其中倍增演算法只有25行，DC3演算法只有40行。 1.1、基本定義 　　子串：字元串S的子串r[i..j]，i≤j，表示r串中從i到j這一段，也就是順次排列r[i]，r[i+1]，...，r[j]形成的字元串。 　　後綴：後綴是指從某個位置i開始到整個串末尾結束的一個特殊子串。字元串r的從第i個字元開始的後綴表示為Suffix(i)，也就是Suffix(i)=r[i..len(r)]。 　　大小比較：關於字元串的大小比較，是指通常所說的「字典順序」比較，也就是對於兩個字元串u、v，令i從1開始順次比較u[i]和v[i]，如果u[i]=v[i]則令i加1，否則若u[i]v[i]則認為u>v（也就是vlen(u)或者 i>len(v)仍比較不出結果，那麼若len(u)len(v)則 u>v。 　　從字元串的大小比較的定義來看，S的兩個開頭位置不同的後綴 u和v進行比較的結果不可能是相等，因為 u=v的必要條件len(u)=len(v)在這裡不可能滿足。 　　後綴數組：後綴數組SA是一個一維數組，它保存1..n的某個排列SA[1]，SA[2]，……，SA[n]，並且保證 Suffix(SA[i])=0;i--) sa[--ws[x[i]]]=i; for(j=1,p=1;p=j) y[p++]=sa[i]-j; for(i=0;i=0;i--) sa[--ws[wv[i]]]=y[i]; for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i=0;i--) sa[--ws[x[i]]]=i; 　　這裡x數組保存的值相當於是rank值。下面的操作只是用x數組來比較字元的大小，所以沒有必要求出當前真實的rank值。 　　接下來進行若干次基數排序，在實現的時候，這裡有一個小優化。基數排序要分兩次，第一次是對第二關鍵字排序，第二次是對第一關鍵字排序。對第二關鍵字排序的結果實際上可以利用上一次求得的sa直接算出，沒有必要再算一次。代碼： for(p=0,i=n-j;i=j) y[p++]=sa[i]-j; 　　其中變數j是當前字元串的長度，數組y保存的是對第二關鍵字排序的結果。然後要對第一關鍵字進行排序，代碼： for(i=0;i=0;i--) sa[--ws[wv[i]]]=y[i]; 　　這樣便求出了新的sa值。在求出sa後，下一步是計算rank值。這裡要注意的是，可能有多個字元串的rank值是相同的，所以必須比較兩個字元串是否完全相同，y數組的值已經沒有必要保存，為了節省空間，這裡用y數組保存rank值。這裡又有一個小優化，將x和y定義為指針類型，複製整個數組的操作可以用交換指針的值代替，不必將數組中值一個一個的複製。代碼： for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i=0;i--) b[--ws[wv[i]]]=a[i]; return; } void dc3(int *r,int *sa,int n,int m) { int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p; r[n]=r[n+1]=0; for(i=0;i=0;i--) b[--ws[wv[i]]]=a[i]; return; } 　　基數排序結束後，新的字元的排名保存在 wb數組中。 　　跟倍增演算法一樣，在基數排序以後，求新的字元串時要判斷兩個字元組是否完全相同。代碼： for(p=1,rn[F(wb[0])]=0,i=1; i1，如果h[i-1]≤1，原式顯然成立）並且suffix(k+1)和suffix(i)的最長公共前綴是h[i-1]-1，所以suffix(i)和在它前一名的後綴的最長公共前綴至少是h[i-1]-1。按照h[1]，h[2]，……，h[n]的順序計算，並利用h數組的性質，時間複雜度可以降為O(n)。 　　具體實現： 　　實現的時候其實沒有必要保存h數組，只須按照h[1]，h[2]，……，h[n]的順序計算即可。代碼： int rank[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