2011年軟考程序員考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理(16)

　　更多：2011年軟考程序員考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理匯總

　　20、后綴數(shù)組

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

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

　　后綴數(shù)組：后綴數(shù)組SA 是一個(gè)一維數(shù)組，它保存1..n 的某個(gè)排列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)在所有后綴中從小到大排列的“名次”。

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

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

　　倍增算法構(gòu)建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];

　　}

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

　　//越界了，因?yàn)閥[a]= y[b]就暗含了他們長(zhǎng)度相等，都沒(méi)有包含最后一位。

　　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++)//對(duì)字符排序不會(huì)超過(guò)255，根據(jù)實(shí)際情況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;

　　//這段代碼用到桶排序思想，就是先進(jìn)桶，再?gòu)牟煌�桶里一個(gè)一個(gè)往外倒

　　//sa[]保存的是1-前綴排序結(jié)果，Rank_x[]保存的是1-前綴時(shí)的各位置的排名

　　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;

　　//這段代碼對(duì)1-前綴時(shí)做第二關(guān)鍵字排序

　　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];

　　//又用到了一次桶排序，注意體會(huì)，是在對(duì)第二關(guān)鍵字排好序的序列上對(duì)

　　//第一關(guān)鍵字進(jìn)行桶排序求得了新的sa[]，result_x[]保存的是關(guān)于第二關(guān)鍵字

　　//排好序的序列的第一關(guān)鍵字排名，為桶排序做好準(zhǔn)備

　　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)名次可能一樣，當(dāng)名次各不一樣時(shí)就是排序完成時(shí)。

　　}

　　}

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

　　2011年上半年軟考報(bào)名時(shí)間及方式匯總

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