題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)只含有 ' a ' 和 ' b ' 的字符串，再給出 B 數(shù)組的構(gòu)造方法如下：對于每個(gè)位置 i 來說

如果存在一個(gè)位置 j ，使得 j < i 且 s[ j ] == s[ i ] ，則 b[ i ] = i - j

否則 s[ i ] = 0

現(xiàn)在需要對字符串的每個(gè)后綴構(gòu)造 B 數(shù)組，并按照字典序排序

題目分析：參考博客：https://blog.csdn.net/weixin_43965698/article/details/107304525

一個(gè)例子：

通過觀察，可以將每個(gè)后綴的 B 數(shù)組分成兩段，分別記為段 A 和段 B（上圖中表示為段 A 和段 D ）

段 A 的特點(diǎn)是：第一個(gè)數(shù)字和最后一個(gè)數(shù)字同為 0，且段 A 中只有這兩個(gè) 0，段 B 的特點(diǎn)是：是字符串 s 的 B 數(shù)組的其中一個(gè)后綴

因?yàn)橹挥卸?A 中含有 0 ，所以在排序時(shí)，段 A 的優(yōu)先級要高于段 B 的，所以段 A 長度更小的，顯然應(yīng)該排在前面

當(dāng)段 A 的長度相等時(shí)，再考慮段 B ，因?yàn)榇藭r(shí)的段 B 都是字符串 s 的 B 數(shù)組的后綴，所以可以利用后綴數(shù)組得到 rk 數(shù)組，rk[ i ] 當(dāng)然就是后綴 i 的排名了

當(dāng)然存在特殊情況，就是如果段 B 為空時(shí)，此時(shí)顯然段 B 為空的字典序更小

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;char str[N];int sa[N]; //SA數(shù)組，表示將S的n個(gè)后綴從小到大排序后把排好序的 //的后綴的開頭位置順次放入SA中 int t1[N],t2[N],c[N];int rk[N],height[N],len;int s[N];void build_sa(int s[],int n,int m)//n為添加0后的總長 {int i,j,p,*x=t1,*y=t2;for(i=0;i<m;i++) c[i]=0;for(i=0;i<n;i++) c[x[i]=s[i]]++;for(i=1;i<m;i++) c[i]+=c[i-1];for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;for(j=1;j<=n;j<<=1) {p=0;for(i=n-j;i<n;i++) y[p++]=i;for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;for(i=0;i<m;i++) c[i]=0;for(i=0;i<n;i++) c[x[y[i]]]++;for(i=1;i<m;i++) c[i]+=c[i-1];for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];swap(x,y);p=1,x[sa[0]]=0;for(i=1;i<n;i++) x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+j]==y[sa[i]+j]?p-1:p++;if(p>=n) break;m=p;} }void get_height(int s[],int n)//n為添加0后的總長 {int i,j,k=0;for(i=0;i<=n;i++)rk[sa[i]]=i;for(i=0;i<n;i++) {if(k) k--;j=sa[rk[i]-1];while(s[i+k]==s[j+k]) k++;height[rk[i]]=k;} }void solve(int base=128) {build_sa(s,len+1,base);get_height(s,len); }struct Node {int id,len_a,pos_b;//id:編號,len_a:段A的長度,pos_b:段B的起始位置 Node(int id,int len_a,int pos_b):id(id),len_a(len_a),pos_b(pos_b){}bool operator<(const Node& t)const{if(len_a!=t.len_a)//如果段A的長度不相等，較短的字典序更短 return len_a<t.len_a;if(pos_b!=-1&&t.pos_b!=-1)//如果都有段B，直接根據(jù)后綴數(shù)組比較大小 return rk[pos_b]<rk[t.pos_b];return pos_b==-1;//否則沒有段B的顯然更小 } };int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);while(scanf("%d",&len)!=EOF){scanf("%s",str);int pre_a=-1,pre_b=-1;for(int i=0;i<len;i++)//根據(jù)題目要求初始化s數(shù)組 {if(str[i]=='a'){if(pre_a==-1)s[i]=1;elses[i]=i-pre_a+1;pre_a=i;}else{if(pre_b==-1)s[i]=1;elses[i]=i-pre_b+1;pre_b=i;}}s[len]=0;solve(len+1);pre_a=pre_b=-1;vector<Node>ans;for(int i=len-1;i>=0;i--){if(str[i]=='a'){if(pre_b==-1)//如果a之后沒再有b的話，說明不存在段B，設(shè)置起初始位置為-1，設(shè)置段A的長度為len-i+1 ans.push_back(Node(i,len-i+1,-1));else//如果同時(shí)存在段A和段B，記錄段A的長度和段B的初始位置 ans.push_back(Node(i,pre_b-i+1,pre_b+1));pre_a=i;}else{if(pre_a==-1)ans.push_back(Node(i,len-i+1,-1));elseans.push_back(Node(i,pre_a-i+1,pre_a+1));pre_b=i;}}sort(ans.begin(),ans.end());for(auto v:ans)printf("%d ",v.id+1);puts("");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的牛客多校 - B-Suffix Array(后缀数组)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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