?

后綴數(shù)組sa(x)表示排序后第x位在排序前的位置。

這個(gè)東西的求法有兩種，一種是倍增，時(shí)間復(fù)雜度o(n log n)或o(n log²n)，另一種是用不知道什么方法做到的o(n)。

至于第二種方法是什么，并不對勁的人并不知道，所以只說倍增。

考慮正常地比較兩個(gè)字符串，都是從頭比較到尾：

?

那么，如果把兩個(gè)字符串都斷成兩半，并且已知每一段的排名，就相當(dāng)于以第一段為第一關(guān)鍵字，第二段為第二關(guān)鍵字排序了。

根據(jù)這個(gè)性質(zhì)，就能想到如果先把字符串的每個(gè)位置開始長度為一的子串進(jìn)行排序后，就能在至多n log n的時(shí)間內(nèi)將每個(gè)位置開始長度為二的子串排序。

↑大概長這樣，注意最后要補(bǔ)一個(gè)空字符。

以此類推，就能這樣倍增地求出后綴的排序了，還是要注意最后補(bǔ)空字符。

如果用基數(shù)排序，每次排序的時(shí)間復(fù)雜度是o(n)的，那么總復(fù)雜度就是o(n log n)了。

如果用快速排序，總復(fù)雜度就是o(n log²n)，心中有黨常數(shù)極小才能過。

#include<algorithm> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<iomanip> #include<iostream> #include<map> #include<queue> #include<stack> #include<vector> #define rep(i,x,y) for(register int i=(x);i<=(y);++i) #define dwn(i,x,y) for(register int i=(x);i>=(y);--i) #define re register #define maxn 2000010 using namespace std; inline int read() {int xx=0,ff=1;char ch=getchar();while(isdigit(ch)==0&&ch!='-')ch=getchar();if(ch=='-')ff=-1,ch=getchar();while(isdigit(ch))xx=xx*10+ch-'0',ch=getchar();return xx*ff; } void write(int x) {int ff=0;char ch[15];if(x<0){x=-x;putchar('-');}while(x)ch[++ff]=(x%10)+'0',x/=10;if(ff==0)putchar('0');while(ff)putchar(ch[ff--]);putchar(' '); } int sa[maxn],ord[maxn],rnk[maxn],n,m; int sum[maxn]; char s[maxn]; int main() {scanf("%s",s+1);n=strlen(s+1);m=130;rep(i,1,n)sum[rnk[i]=s[i]]++;rep(i,1,m)sum[i]+=sum[i-1];dwn(i,n,1)sa[sum[rnk[i]]--]=i;for (int k=1;k<=n;k<<=1) { //從這里開始到分界線是更新sa的部分 int p=0;rep(i,n-k+1,n)ord[++p]=i;rep(i,1,n)if(sa[i]>=k+1)ord[++p]=sa[i]-k;//ord[i]表示按第二關(guān)鍵字排名后排在第i位的在原串中的位置//需要注意的是，原串中的第n-k+1到n位置上的后綴由于加上k后的位置在超過n的地方，需要補(bǔ)空字符//這里假設(shè)空字符是最小的，所以按第二關(guān)鍵字排序后，第n-k+1到n位置上的后綴排在最前面 rep(i,0,m)sum[i]=0;rep(i,1,n)sum[rnk[i]]++;//計(jì)算不同的排名出現(xiàn)了多少次 rep(i,1,m)sum[i]+=sum[i-1];//算前綴和。c[i]表示排名為i的串最后一次出現(xiàn)在排序后的第幾名（當(dāng)k<n時(shí)可能在s中有很多個(gè)排名相同的） dwn(i,n,1)sa[sum[rnk[ord[i]]]--]=ord[i];//rnk[ord[i]]表示排序后第i個(gè)的排名（可能會(huì)重）是多少 //不能直接寫sa[sum[rnk[i]]--]=i//交換前，x[i]表示從i開始的后綴在上一輪的排名//——————————分界線————————————//從這里開始是更新x的部分 swap(rnk,ord);p=1,rnk[sa[1]]=1;rep(i,2,n)rnk[sa[i]]=(ord[sa[i-1]]==ord[sa[i]]&&ord[sa[i-1]+k]==ord[sa[i]+k])?p:++p;if(p>=n)break;m=p;}rep(i,1,n)write(sa[i]);return 0; }

　　

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

總結(jié)

以上是生活随笔為你收集整理的并不对劲的后缀数组的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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