題目

我還會寫\(SA\)和 \(ST\)表真是令人感動

發現這是一個思博題

我們開一個指針，標記一下當前合法的字典序最小的后綴排名在哪里，剛開始自然是\(1\)

我們發現這個后綴不能為我們提供\(i\)的長度我們就右移這個指針

之后我們二分+\(St\)表找到從這個后綴往右擴展的最大距離，查一下這里面最小的\(sa\)就好了

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define re register #define LL long long #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) const int maxn=300005; inline int read() {char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x; } char S[maxn]; int sa[maxn],het[maxn],rk[maxn],tp[maxn],tax[maxn]; int c[maxn],a[maxn]; int n,opt,m,sz; int log_2[maxn],St[maxn][20],v[maxn][20]; inline int find(int x) {int l=1,r=sz;while(l<=r) {int mid=l+r>>1;if(c[mid]==x) return mid;if(c[mid]<x) l=mid+1;else r=mid-1;}return 0; } inline void qsort() {for(re int i=0;i<=m;i++) tax[i]=0;for(re int i=1;i<=n;i++) tax[rk[i]]++;for(re int i=1;i<=m;i++) tax[i]+=tax[i-1];for(re int i=n;i;i--) sa[tax[rk[tp[i]]]--]=tp[i]; } inline int query(int l,int r) {int k=log_2[r-l+1];return min(St[l][k],St[r-(1<<k)+1][k]); } inline int ask(int l,int r) {int k=log_2[r-l+1]; return min(v[l][k],v[r-(1<<k)+1][k]); } int main() {opt=read(),n=read();if(opt==26) {scanf("%s",S+1);for(re int i=1;i<=n;i++) a[i]=S[i]-'a';}else for(re int i=1;i<=n;i++) a[i]=read();for(re int i=1;i<=n;i++) c[i]=a[i];std::sort(c+1,c+n+1);sz=std::unique(c+1,c+n+1)-c-1;for(re int i=1;i<=n;i++) a[i]=find(a[i]);for(re int i=1;i<=n;i++) rk[i]=a[i],tp[i]=i;m=sz;qsort();for(re int w=1,p=0;p<n;m=p,w<<=1) {p=0;for(re int i=1;i<=w;i++) tp[++p]=n-w+i;for(re int i=1;i<=n;i++) if(sa[i]>w) tp[++p]=sa[i]-w;qsort();for(re int i=1;i<=n;i++) std::swap(rk[i],tp[i]);rk[sa[1]]=p=1;for(re int i=2;i<=n;i++)rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+w]==tp[sa[i-1]+w])?p:++p;}int k=0;for(re int i=1;i<=n;i++) {if(k) --k;int j=sa[rk[i]-1];while(a[i+k]==a[j+k]) ++k;het[rk[i]]=k;}for(re int i=1;i<=n;i++) St[i][0]=het[i];for(re int i=2;i<=n;i++) log_2[i]=log_2[i>>1]+1;for(re int j=1;j<=log_2[n];j++) for(re int i=1;i+(1<<j)-1<=n;i++)St[i][j]=min(St[i][j-1],St[i+(1<<(j-1))][j-1]);for(re int i=1;i<=n;i++) v[i][0]=sa[i];for(re int j=1;j<=log_2[n];j++)for(re int i=1;i+(1<<j)-1<=n;i++)v[i][j]=min(v[i][j-1],v[i+(1<<(j-1))][j-1]);int now=1;for(re int i=1;i<=n;i++) {while(sa[now]+i-1>n) now++;int l=2,r=n-now+1;int ans=1;while(l<=r) {int mid=l+r>>1;if(query(now+1,now+mid-1)>=i) ans=mid,l=mid+1;else r=mid-1;}printf("%d ",ask(now,now+ans-1));}return 0; }

轉載于:https://www.cnblogs.com/asuldb/p/10562757.html

總結

以上是生活随笔為你收集整理的【LGP5108】仰望半月的夜空的全部內容，希望文章能夠幫你解決所遇到的問題。

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