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

　　更多：2011年軟考程序員考試復習筆試知識點整理匯總

　　20、后綴數(shù)組

　　(1)什么是后綴數(shù)組呢?

　　直觀來說，后綴數(shù)組是記錄一個字符串的后綴的排名的數(shù)組，什么是后綴呢，設一個字符串的長度是len(我們約定字符串下標從0開始，所以到len-1結束，比較符合我們?nèi)粘＞幊塘晳T)，某一位置i的后綴的就是從i開始到len-1結束的字符串，用suffix(i)表示，即對字符串s來說，suffix(i) =s[i,i+1....len-1]，可以發(fā)現(xiàn)不同的后綴按字典序排列的名詞是不一樣的(什么是字典序都應該知道吧)，記錄這些后綴按字典序排好的結果的數(shù)組就叫后綴數(shù)組，一般用sa[]表示，網(wǎng)絡上對sa[]的標準定義為：

　　后綴數(shù)組：后綴數(shù)組SA 是一個一維數(shù)組，它保存1..n 的某個排列SA[1]，SA[2]，……，SA[n]，并且保證Suffix(SA[i])< Suffix(SA[i+1])，1≤i

　　另外還要用到排名數(shù)組，即某一位置的后綴在所有后綴中的排名的數(shù)組，一般用Rank[]表示，容易發(fā)現(xiàn)Rank[sa[i]]=i。

　　名次數(shù)組：名次數(shù)組Rank[i]保存的是Suffix(i)在所有后綴中從小到大排列的“名次”。

　　簡單的說，后綴數(shù)組是“排第幾的是誰?”，名次數(shù)組是“你排第幾?”。

　　知道了這些定義，剩下的就是如何構建后綴數(shù)組了，可以按照定義來構建，把每個后綴當做一個字符串，用全速排序來排序，不過那樣的時間復雜度為O(n*n)，一般用來構建后綴數(shù)組用的是倍增算法(Doubling Algorithm)，說到倍增算法，就要說到k-前綴的定義，字符串u的k-前綴就是u的從0開始到k-1的字串，u長度不足k時就是整個字符串u，這樣一來我們在比較串s的兩個位置i,j的后綴的2k-前綴時，就是比較兩個后綴的k-前綴和兩個后綴位置+k的k-前綴，顯然當k=1時就是對整個串的單字符進行排序，復雜度O(nlogn)，當k>=2時對已排好的k-前綴進行排序，用快排，復雜度O(nlogn)，用基數(shù)排序，復雜度O(n)，容易發(fā)現(xiàn)k是2倍增的。所以整個過程的時間復雜度就是O(nlongn)。

　　倍增算法構建sa[]的代碼如下：

　　#definemax 10000

　　intRx[max],Ry[max],rx[max];

　　intcmp(int *y,int a,int b,int l)

　　{

　　return y[a] == y[b] && y[a+l] +y[b+l];

　　}

　　//對于串約定最后一位是小于串中其他任何元素的元素，這樣cmp的時候就不用擔心y[a+l]

　　//越界了，因為y[a]= y[b]就暗含了他們長度相等，都沒有包含最后一位。

　　voidget_sa(char *s,int *sa)

　　{

　　int len = strlen(s),*Rank_x = Rx,*Rank_y =Ry,bar[max],*result_x = rx;

　　int i,j,k,p,*t,m=255;

　　for (i = 0; i<= m; i++)//對字符排序不會超過255，根據(jù)實際情況m值自定

　　bar[i] = 0;

　　for (i = 0; i< len; i++) bar[Rank_x[i] =s[i]]++;

　　for (i = 1; i<= m; i++) bar[i] +=bar[i-1];

　　for (i = len-1; i>= 0; i--)sa[--bar[Rank_x[i]]] = i;

　　//這段代碼用到桶排序思想，就是先進桶，再從不同桶里一個一個往外倒

　　//sa[]保存的是1-前綴排序結果，Rank_x[]保存的是1-前綴時的各位置的排名

　　for (k = 1,p = 1; p < len; k *= 2, m = p)

　　{

　　for (p = 0,i = len - k; i < len;i++) Rank_y[p++] = i;

　　for (i = 0; i< len; i++) if (sa[i]>= k) Rank_y[p++] = sa[i] - k;

　　//這段代碼對1-前綴時做第二關鍵字排序

　　for (i = 0; i< len; i++) result_x[i]= Rank_x[Rank_y[i]];

　　for (i = 0; i<= m; i++) bar[i] =0;

　　for (i = 0; i< len; i++)bar[result_x[i]]++;

　　for (i = 1; i<= m; i++) bar[i] +=bar[i-1];

　　for (i = len-1; i>= 0; i--)sa[--bar[result_x[i]]] = Rank_y[i];

　　//又用到了一次桶排序，注意體會，是在對第二關鍵字排好序的序列上對

　　//第一關鍵字進行桶排序求得了新的sa[]，result_x[]保存的是關于第二關鍵字

　　//排好序的序列的第一關鍵字排名，為桶排序做好準備

　　for (t = Rank_x,Rank_x = Rank_y,Rank_y= t,p = 1,Rank_x[sa[0]]= 0,i = 1; i

　　Rank[sa[i]] =cmp(Rank_y,sa[i],sa[i-1],k)?p-1:p++;

　　//求新的名次數(shù)組，可以發(fā)現(xiàn)名次可能一樣，當名次各不一樣時就是排序完成時。

　　}

　　}

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

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

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