后缀数组用来处理一类字符串问题
学习博客
https://www.cnblogs.com/victorique/p/8480093.html#autoid-1-2-1
例题1 ：hihocoder #1403 后缀数组一 重复旋律
最长可重叠重复K次子串问题
转化为求 height 数组中长度为 k-1 的子序列的最小值，单调队列维护即可
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> #include<stack> #include<queue> using namespace std; typedef long long ll; const int maxn = 20020; const int maxm = 110; int n,m,t,ans; int a[maxn]; int c[maxn],sa[maxn],rk[maxn],x[maxn],y[maxn],height[maxn]; int head,tail,q[maxn],p[maxn]; void get_sa(){ for(int i=1;i<=n;i++) x[i]=a[i],++c[x[i]]; for(int i=2;i<=m;i++) c[i]+=c[i-1]; for(int i=1;i<=n;i++) sa[c[x[i]]--]=i; for(int k=1;k<=n;k<<=1){ int num=0; for(int i=n-k+1;i<=n;i++) y[++num]=i; for(int i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k; for(int i=1;i<=m;i++) c[i]=0; for(int i=1;i<=n;i++) ++c[x[i]]; for(int i=2;i<=m;i++) c[i]+=c[i-1]; for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i],y[i]=0; swap(x,y); x[sa[1]]=1; num=1; for(int i=2;i<=n;i++){ x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k])?num:++num; } if(num==n) break; m=num; } } void get_height(){ int k=0; for(int i=1;i<=n;i++) rk[sa[i]]=i; for(int i=1;i<=n;i++){ if(rk[i]==1) continue; if(k) k--; int j=sa[rk[i]-1]; while(i+k<=n && j+k<=n && a[i+k]==a[j+k]) k++; height[rk[i]]=k; } } ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<‘0‘ || ch>‘9‘){ if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘ && ch<=‘9‘){ s=s*10+ch-‘0‘; ch=getchar(); } return s*f; } int main(){ n=read(),t=read(),m=100; for(int i=1;i<=n;i++) a[i]=read(); get_sa(); get_height(); // for(int i=1;i<=n;i++) printf("%d ",height[i]); head=0,tail=1; t--; if(t==0){ printf("%d\n",n); return 0; } for(int i=1;i<=n;i++){ while(head<=tail && q[tail]>height[i]) --tail; q[++tail]=height[i]; p[tail]=i; while(p[head]<i-t+1) head++; if(i>=t) ans=max(ans,q[head]); } printf("%d\n",ans); return 0; }
例题2 ：hihocoder #1407 后缀数组二 重复旋律2
最长不可重叠重复子串问题
height数组不好直接来判断是否有重合，转化为二分判断性问题，二分一个k，表示我们假设串中存在长度为k的不可重叠重复子串，
遍历 height数组，如果相邻的 height>=k，则将其分为一组，如果一组中 maxsa-minsa>=k 的话，则成立
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> #include<stack> #include<queue> using namespace std; typedef long long ll; const int maxn = 101000; int n,m; int a[maxn],sa[maxn],rk[maxn],c[maxn],x[maxn],y[maxn],height[maxn]; void get_sa(){ for(int i=1;i<=n;i++) x[i]=a[i],++c[x[i]]; for(int i=2;i<=m;i++) c[i]+=c[i-1]; for(int i=1;i<=n;i++) sa[c[x[i]]--]=i; for(int k=1;k<=n;k<<=1){ int num=0; for(int i=n-k+1;i<=n;i++) y[++num]=i; for(int i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k; for(int i=1;i<=m;i++) c[i]=0; for(int i=1;i<=n;i++) ++c[x[i]]; for(int i=2;i<=m;i++) c[i]+=c[i-1]; for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i],y[i]=0; swap(x,y); x[sa[1]]=1; num=1; for(int i=2;i<=n;i++){ x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k])?num:++num; } if(num==n) break; m=num; } } void get_height(){ int k=0; for(int i=1;i<=n;i++) rk[sa[i]]=i; for(int i=1;i<=n;i++){ if(rk[i]==1) continue; if(k) k--; int j=sa[rk[i]-1]; while(i+k<=n && j+k<=n && a[i+k]==a[j+k]) k++; height[rk[i]]=k; } } bool check(int k){ int minsa,maxsa; for(int i=1;i<=n;i++){ if(height[i]<k){ minsa=sa[i]; maxsa=sa[i]; }else{ minsa=min(minsa,sa[i]); maxsa=max(maxsa,sa[i]); } if(maxsa-minsa>=k) return true; } return false; } ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<‘0‘ || ch>‘9‘){ if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘ && ch<=‘9‘){ s=s*10+ch-‘0‘; ch=getchar(); } return s*f; } int main(){ n=read(),m=1000; for(int i=1;i<=n;i++) a[i]=read(); get_sa(); get_height(); // for(int i=1;i<=n;i++) printf("%d ",height[i]); int L=0,R=n,ans; while(L<=R){ int mid=(L+R)/2; if(check(mid)){ ans=mid; L=mid+1; }else{ R=mid-1; } } printf("%d\n",ans); return 0; }
原文：https://www.cnblogs.com/tuchen/p/10360100.html