后綴排序

Description

Tim正在自學(xué)《數(shù)據(jù)結(jié)構(gòu)》，他剛剛學(xué)會(huì)如何比較兩個(gè)字符串大小。書(shū)上是這么說(shuō)的（和Pascal語(yǔ)言中的比較規(guī)則相同，學(xué)習(xí)過(guò)Pascal語(yǔ)言的同學(xué)可以跳過(guò)這段）：?
比較兩個(gè)不同字符串s1=’p1p2p3…pN’和s2=’q1q2q3…qM’的大小，設(shè)N<=M。?
若s1是s2的前綴，則s1<s2。否則設(shè)pi<>qi，且i最小；若pi<qi，則s1<s2，否則s1>s2。?
Tim想通過(guò)練習(xí)熟練運(yùn)用這個(gè)規(guī)則，于是打算出許多字符串，并將它們從小到大排序。可是Tim非常懶，隨機(jī)寫(xiě)出 K個(gè)很長(zhǎng)的字符串實(shí)在是太麻煩了。不過(guò)聰明的他想到了一個(gè)好辦法，他寫(xiě)了一個(gè)很長(zhǎng)的字符串，自言自語(yǔ)說(shuō)，“我只要把這個(gè)字符串的所有后綴從小到大排序就可以了”。?

Input

輸入文件suffix.in中僅有一行，且是一個(gè)僅包含小寫(xiě)字母的字符串，長(zhǎng)度K不超過(guò)10^5。?

Output

有K行，每行一個(gè)數(shù)字，第i行的數(shù)字Pi表示所有后綴中，第i小的是由原字符串第Pi個(gè)字符引導(dǎo)的后綴。?

Sample Input

?

mississippi

?

Sample Output

?

11 8 5 2 1 10 9 7 4 6 3

?

Source

Oibh（后綴數(shù)組）

?

?

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

?

也就是將S 的n 個(gè)后綴從小到大進(jìn)行排序之后把排好序的后綴的開(kāi)頭位置順次放入SA 中。

?

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

?

倍增算法求后綴數(shù)組的主要思路是：用倍增的方法對(duì)每個(gè)字符開(kāi)始的長(zhǎng)度為2k 的子字
符串進(jìn)行排序，求出排名，即rank 值。k 從0 開(kāi)始，每次加1，當(dāng)2k 大于n 以
后，每個(gè)字符開(kāi)始的長(zhǎng)度為2k 的子字符串便相當(dāng)于所有的后綴。并且這些子字
符串都一定已經(jīng)比較出大小，即rank 值中沒(méi)有相同的值，那么此時(shí)的rank 值就
是最后的結(jié)果。每一次排序都利用上次長(zhǎng)度為2k-1 的字符串的rank 值，那么長(zhǎng)
度為2k 的字符串就可以用兩個(gè)長(zhǎng)度為2k-1 的字符串的排名作為關(guān)鍵字表示，然
后進(jìn)行基數(shù)排序，便得出了長(zhǎng)度為2k 的字符串的rank 值。以字符串“aabaaaab”
為例，整個(gè)過(guò)程如圖2 所示。其中x、y 是表示長(zhǎng)度為2k 的字符串的兩個(gè)關(guān)鍵字。

?

?

?

code:
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<cstring> 5 #define maxn 100010 6 using namespace std; 7 char s[maxn]; 8 int n,m,tot,sum[maxn],t1[maxn],t2[maxn],rank[maxn],SA[maxn]; 9 void get_SA(){ 10 int *x=t1,*y=t2; 11 for (int i=1;i<=n;i++) sum[x[i]=s[i]]++; 12 for (int i=1;i<=255;i++) sum[i]+=sum[i-1]; 13 for (int i=1;i<=n;i++) SA[sum[x[i]]--]=i; 14 tot=0; 15 for (int len=1;tot<n;len<<=1,m=tot){ 16 tot=0; 17 for (int i=n-len+1;i<=n;i++) y[++tot]=i; 18 for (int i=1;i<=n;i++) if (SA[i]>len) y[++tot]=SA[i]-len; 19 for (int i=1;i<=m;i++) sum[i]=0; 20 for (int i=1;i<=n;i++) sum[x[y[i]]]++; 21 for (int i=1;i<=m;i++) sum[i]+=sum[i-1]; 22 for (int i=n;i>=1;i--) SA[sum[x[y[i]]]--]=y[i]; 23 swap(x,y); 24 x[SA[1]]=tot=1; 25 for (int i=2;i<=n;i++){ 26 if (y[SA[i]]!=y[SA[i-1]]||y[SA[i]+len]!=y[SA[i-1]+len]) tot++; 27 x[SA[i]]=tot; 28 } 29 } 30 for (int i=1;i<=n;i++) rank[i]=x[i]; 31 } 32 int main(){ 33 scanf("%s",s+1); 34 n=strlen(s+1),m=123; 35 get_SA(); 36 for (int i=1;i<=n;i++) printf("%d\n",SA[i]); 37 return 0; 38 } 39

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/chenyushuo/p/4124794.html

總結(jié)

以上是生活随笔為你收集整理的初学后缀数组的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。