寫在前面：

多余的我就不提了，只是覺得網上的博客吧流程，每個數組存的是下標還是值，都講的不是很清楚（讓我這種蒟蒻很是困擾）

相信到現在這種水平的都可以知道什么是倍增，為什么能倍增都比較清楚了，但是代碼實現總感覺怪怪的…… 本文的定位就是想把代碼實現的部分講清楚…… 現在請聽我娓娓道來……

清爽代碼：

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int MAX=1e6+5; int n,m; int tax[MAX],rak[MAX],tp[MAX],sa[MAX]; char s[MAX];void sort(int a[],int b[]){for(int i=0;i<=m;i++)tax[i]=0;for(int i=1;i<=n;i++)tax[a[i]]++;for(int i=1;i<=m;i++)tax[i]+=tax[i-1];for(int i=n;i>=1;i--)sa[tax[a[b[i]]]--]=b[i]; }bool comp(int r[],int a,int b,int k){return r[a]==r[b]&&r[a+k]==r[b+k]; }void get_sa(int a[],int b[]){for(int i=1;i<=n;i++)m=max(m,a[i]=s[i]-'0'),b[i]=i;sort(a,b);for(int p=0,j=1;p<n;j<<=1,m=p){p=0;for(int i=1;i<=j;i++)b[++p]=n-j+i;for(int i=1;i<=n;i++)if(sa[i]>j)b[++p]=sa[i]-j;sort(a,b);int *t=a;a=b;b=t;a[sa[1]]=p=1;for(int i=2;i<=n;i++)a[sa[i]]=comp(b,sa[i],sa[i-1],j)?p:++p;} }int main(){scanf("%s",s+1);n=strlen(s+1);get_sa(rak,tp);for(int i=1;i<=n;i++)printf("%d ",sa[i]); }

洛谷模板：后綴排序

一些定義：

看了上面的代碼，你應該對后綴數組有了一個初步的印象吧（復雜、玄學而又美麗的代碼）

我們先看看數組的定義：

sa[i]=j ，表示第 i 名的后綴是從 j 開始的（注意存的是下標）

rank[i]=j ，從 i 開始的后綴是第 j 名的（和 sa 互逆，是排名（值））

tp[i] (b[i]) =j，第二關鍵字為 i 的后綴是從 j 開始的 （相當于是第二關鍵字的 sa 數組，存的是下標）

tax[i]=j，表示第一關鍵字為 i 的數，有 j 個（基數排序時用的桶，是值）

知道了這些，相信你可以初步理解了吧（我都不信）

我們看看后綴排序的流程

這是算法的具體流程，但是為什么跟上面的代碼似乎看不出來有什么聯系……

我們把現在就把代碼都解剖一下，細嚼慢咽食用更佳。

基數排序

當然你可以想到，我們是否能把關鍵字放到 pair 里，sort 一遍不就行了？

但是這樣是 \(log^2\) 的，不是那么優秀，我們可以用一種比 sort 更快的方法——基數排序。

void sort(int a[],int b[]){for(int i=0;i<=m;i++)tax[i]=0;for(int i=1;i<=n;i++)tax[a[i]]++;for(int i=1;i<=m;i++)tax[i]+=tax[i-1];for(int i=n;i>=1;i--)sa[tax[a[b[i]]]--]=b[i]; }

別看他有這么一個高大尚的名字，其實他和桶排是同一個媽生的……

看代碼：（n是字符串長度，m是數字的總數）

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

桶清零，不用說……

for(int i=1;i<=n;i++)tax[a[i]]++;

每個數放進各自的桶……

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

加上前邊的桶的值，也就是現在這個值的排名……

for(int i=n;i>=1;i--)sa[tax[a[b[i]]]--]=b[i];

這行挺復雜
第一關鍵字（a 那層），第二關鍵字從大到小（b 那層），的桶內有多少個數（tax 那層），現在的這名，就是 b[i]（sa 那層），然后桶內的數就減去一。

說的有點繞……這真心不好解釋（可能是我的語言表達能力欠佳吧）

剩下的……

for(int p=0,j=1;p<n;j<<=1,m=p)

倍增嘛（又是這圖）

for(int i=1;i<=j;i++)b[++p]=n-j+i; for(int i=1;i<=n;i++)if(sa[i]>j)b[++p]=sa[i]-j;

這是更新第而關鍵字
第一個for，就是說后面越界的數關鍵字為零，當然排在前面。
第二個for，按排名，如果這個后綴在 j 后，就能做為 sa[i]-j 的第二關鍵字。

sort(a,b); int *t=a;a=b;b=t; a[sa[1]]=p=1; for(int i=2;i<=n;i++) a[sa[i]]=comp(b,sa[i],sa[i-1],j)?p:++p;

基數排序并更新第一關鍵字。
swap 一下只是因為不想多開一個數組，沒有別的意思，現在 a 是新關鍵字，b 是舊關鍵字。
第一名的第一關鍵字肯定是 1 啦。
從二開始，如果現在的這名和前一名的兩個關鍵字相等就是并列，否則就排到后一名。

comp 代碼……

bool comp(int r[],int a,int b,int k){return r[a]==r[b]&&r[a+k]==r[b+k]; }

完了嗎？

后綴排序的部分到這里就已經結束了……

但是光有個后綴排序有什么實質性的用處嗎？

了解過的同學應該知道，有這么一個 height 數組，height[i] 表示的是，排名為 i 的后綴與排名為 i-1 的后綴的 LCP（最長公共前綴）

有了這個東東，就可以在后綴數組上亂搞，許多問題都能迎刃而解……

但怎么求是個問題，樸素的 \(n^2\) …… 算了吧

我們有這樣一個性質 \(height[i+1] \ge height[i]-1\)

根據這樣的性質，可以 \(O(n)\) 求 height

for(int i=1,j=0;i<=n;i++){if(j)j--;while(s[i+j]==s[sa[rak[i]-1]+j])j++;height[rak[i]]=j; }

好了真的完了，這里不多說理論，目的只是填一下代碼實現的坑，后綴數組的模板代碼已經完了，希望有助于大家理解，再也不用痛苦的背板了……（卒）

轉載于:https://www.cnblogs.com/ezoiLZH/p/9607849.html

總結

以上是生活随笔為你收集整理的最详细的后缀数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。