學(xué)習(xí)自：https://www.cnblogs.com/victorique/p/8480093.html

后綴：是字符串的一個(gè)特殊子串，以s的第i個(gè)字符為第一個(gè)元素的后綴為suff(i)。

后綴數(shù)組：后綴數(shù)組sa[i]就表示排名為i的后綴的起始位置的下標(biāo)。

相反映射：rk[i]就表示起始位置的下標(biāo)為i的后綴的排名。

倍增法+基數(shù)排序?qū)崿F(xiàn)后綴數(shù)組O（nlogn）排序：思想是先對(duì)首字符排序（重復(fù)），在對(duì)相鄰相加再排序，直到所有排名不同即可。（需進(jìn)一步理解）

?

最長公共前綴：

我們定義LCP(i,j)為suff(sa[i])與suff(sa[j])的最長公共前綴。

LCP(i,j)=LCP(j,i);

LCP(i,i)=len(sa[i])=n-sa[i]+1;

LCP引理

　　LCP(i,k)=min(LCP(i,j),LCP(j,k)) 對(duì)于任意1<=i<=j<=k<=n

LCP定理

　　LCP(i,k)=min(min(LCP(j,j-1))) 對(duì)于1<i<=j<=k<=n

?

重要定理：

我們?cè)O(shè)height[i]為LCP(i,i-1)，1<i<=n，顯然height[1]=0;

由LCP Theorem可得，LCP(i,k)=min(height[j]) i+1<=j<=k

設(shè)h[i]=height[rk[i]]，同樣的，height[i]=h[sa[i]];

有：　　

　　h[i]>=h[i-1]-1;

證明：設(shè)k=rk[i-1]-1.

則有h[i-1] = height[rk[i-1]]=min(LCP(k-1,k-2) )

rk[i-1]<rk[sa[k]]

rk[i]<rk[sa[k]+1]

LCP( i,rk[sa[k]+1] )=h[i-1]-1;

h[i]>=h[i-1];

?

例題：luogu3809 后綴排序

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define rint register int 5 #define inv inline void 6 #define ini inline int 7 #define maxn 1000050 8 using namespace std; 9 char s[maxn]; 10 int y[maxn],x[maxn],c[maxn],sa[maxn],rk[maxn],height[maxn],wt[30]; 11 int n,m; 12 inv putout(int x) { 13 if(!x) { 14 putchar(48); 15 return; 16 } 17 rint l=0; 18 while(x) wt[++l]=x%10,x/=10; 19 while(l) putchar(wt[l--]+48); 20 } 21 inv get_SA() { 22 for (rint i=1; i<=n; ++i) ++c[x[i]=s[i]]; 23 //c數(shù)組是桶 24 //x[i]是第i個(gè)元素的第一關(guān)鍵字 25 for (rint i=2; i<=m; ++i) c[i]+=c[i-1]; 26 //做c的前綴和，我們就可以得出每個(gè)關(guān)鍵字最多是在第幾名 27 for (rint i=n; i>=1; --i) sa[c[x[i]]--]=i; 28 for (rint k=1; k<=n; k<<=1) { 29 rint num=0; 30 for (rint i=n-k+1; i<=n; ++i) y[++num]=i; 31 //y[i]表示第二關(guān)鍵字排名為i的數(shù)，第一關(guān)鍵字的位置 32 //第n-k+1到第n位是沒有第二關(guān)鍵字的 所以排名在最前面 33 for (rint i=1; i<=n; ++i) if (sa[i]>k) y[++num]=sa[i]-k; 34 //排名為i的數(shù) 在數(shù)組中是否在第k位以后 35 //如果滿足(sa[i]>k) 那么它可以作為別人的第二關(guān)鍵字，就把它的第一關(guān)鍵字的位置添加進(jìn)y就行了 36 //所以i枚舉的是第二關(guān)鍵字的排名，第二關(guān)鍵字靠前的先入隊(duì) 37 for (rint i=1; i<=m; ++i) c[i]=0; 38 //初始化c桶 39 for (rint i=1; i<=n; ++i) ++c[x[i]]; 40 //因?yàn)樯弦淮窝h(huán)已經(jīng)算出了這次的第一關(guān)鍵字 所以直接加就行了 41 for (rint i=2; i<=m; ++i) c[i]+=c[i-1]; //第一關(guān)鍵字排名為1~i的數(shù)有多少個(gè) 42 for (rint i=n; i>=1; --i) sa[c[x[y[i]]]--]=y[i],y[i]=0; 43 //因?yàn)閥的順序是按照第二關(guān)鍵字的順序來排的 44 //第二關(guān)鍵字靠后的，在同一個(gè)第一關(guān)鍵字桶中排名越靠后 45 //基數(shù)排序 46 swap(x,y); 47 //這里不用想太多，因?yàn)橐尚碌膞時(shí)要用到舊的，就把舊的復(fù)制下來，沒別的意思 48 x[sa[1]]=1; 49 num=1; 50 for (rint i=2; i<=n; ++i) 51 x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) ? num : ++num; 52 //因?yàn)閟a[i]已經(jīng)排好序了，所以可以按排名枚舉，生成下一次的第一關(guān)鍵字 53 if (num==n) break; 54 m=num; 55 //這里就不用那個(gè)122了，因?yàn)槎加行碌木幪?hào)了 56 } 57 for (rint i=1; i<=n; ++i) putout(sa[i]),putchar(' '); 58 } 59 inv get_height() { 60 rint k=0; 61 for (rint i=1; i<=n; ++i) rk[sa[i]]=i; 62 for (rint i=1; i<=n; ++i) { 63 if (rk[i]==1) continue;//第一名height為0 64 if (k) --k;//h[i]>=h[i-1]+1; 65 rint j=sa[rk[i]-1]; 66 while (j+k<=n && i+k<=n && s[i+k]==s[j+k]) ++k; 67 height[rk[i]]=k;//h[i]=height[rk[i]]; 68 } 69 putchar(10); 70 for (rint i=1; i<=n; ++i) putout(height[i]),putchar(' '); 71 } 72 int main() { 73 gets(s+1); 74 n=strlen(s+1); 75 m=122; 76 //因?yàn)檫@個(gè)題不讀入n和m所以要自己設(shè) 77 //n表示原字符串長度，m表示字符個(gè)數(shù)，ascll('z')=122 78 //我們第一次讀入字符直接不用轉(zhuǎn)化，按原來的ascll碼來就可以了 79 //因?yàn)檗D(zhuǎn)化數(shù)字和大小寫字母還得分類討論，怪麻煩的 80 get_SA(); 81 //get_height(); 82 } View Code

?

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

總結(jié)

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

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