題目鏈接: https://www.lydsy.com/JudgeOnline/problem.php?id=4278

題解:

居然把后綴數(shù)組寫成n^2的。。我真厲害。。

想了無數(shù)種方法，最后發(fā)現(xiàn)就是比后綴字典序排名，后綴數(shù)組即可

注意每個(gè)字符串的結(jié)尾處要加上一個(gè)\(\inf\), 因?yàn)橄喈?dāng)于要把空位盡量后移使得非空位集中在前面

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std;const int N = 4e5+2; const int S = 1e3+1; int sa[N+3]; int rk[N+3]; int tmp[N+3]; int buc[N+3]; int a[N+3]; int ans[N+3]; int n,m;void getSA() {int *x = rk,*y = tmp;for(int i=0; i<=S; i++) buc[i] = 0;for(int i=1; i<=n; i++) buc[x[i]=a[i]]++;for(int i=1; i<=S; i++) buc[i] += buc[i-1];for(int i=n; i>=1; i--) sa[buc[x[i]]--] = i;int p = 0,s = S;for(int j=1; p<n; j<<=1){p = 0;for(int i=n-j+1; i<=n; i++) {y[++p] = i;}for(int i=1; i<=n; i++) {if(sa[i]>j) y[++p] = sa[i]-j;}for(int i=1; i<=s; i++) buc[i] = 0;for(int i=1; i<=n; i++) buc[x[y[i]]]++;for(int i=1; i<=s; i++) buc[i] += buc[i-1];for(int i=n; i>=1; i--) sa[buc[x[y[i]]]--] = y[i];swap(x,y); p = 1; x[sa[1]] = 1;for(int i=2; i<=n; i++) x[sa[i]] = (y[sa[i]]==y[sa[i-1]] && y[sa[i]+j]==y[sa[i-1]+j]) ? p : ++p;s = p;}for(int i=1; i<=n; i++) rk[sa[i]] = i; }int main() {scanf("%d",&n);for(int i=1; i<=n; i++) scanf("%d",&a[i]); a[n+1] = S; n++;scanf("%d",&m);for(int i=n+1; i<=n+m; i++) scanf("%d",&a[i]); a[n+m+1] = S; m++;n += m;getSA();int i = 1,j = n-m+1,k = 1;while(i<n-m && j<n){if(rk[i]<rk[j]) {ans[k] = a[i]; k++; i++;}else {ans[k] = a[j]; k++; j++;}}while(i<n-m) {ans[k] = a[i]; k++; i++;}while(j<n) {ans[k] = a[j]; k++; j++;}for(int i=1; i<n-1; i++) printf("%d ",ans[i]);return 0; }

總結(jié)

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

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