后缀数组用来处理一类字符串问题
学习博客
https://www.cnblogs.com/victorique/p/8480093.html#autoid-1-2-1
求LCP
RMQ，nlogn 预处理，O(1)查询 或者线段树单次查询 O(logn)
void st_init(){ lg[1]=0; for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1; for(int i=1;i<=n;i++) st[i][0]=height[i]; for(int j=1;j<=lg[n];j++){ for(int i=1;i<=n;i++){ st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]); } } } int query(int x,int y){ int len=y-x+1; return min(st[x][lg[len]],st[y-(1<<lg[len])+1][lg[len]]); } int lcp(int x,int y){ int l=min(rk[x],rk[y])+1,r=max(rk[x],rk[y]); return query(l,r); }
例题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; }
例题3 ：hihocoder #1415 后缀数组三 重复旋律3
经典的最长公共子串问题
将两个串合并成一个串，中间添加一个 # 字符，查找相邻且不在同一个字符串中的 height 的最大值
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> #include<stack> #include<queue> using namespace std; typedef long long ll; const int maxn = 201000; int n,m,pos; int sa[maxn],rk[maxn],c[maxn],x[maxn],y[maxn],height[maxn]; char s1[maxn],s2[maxn>>1]; void get_sa(){ for(int i=1;i<=n;i++) x[i]=s1[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 && s1[i+k]==s1[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(){ m=1000; scanf("%s",s1+1); scanf("%s",s2+1); n=strlen(s1+1); pos=n+1; s1[n+1]='#'; int n2=strlen(s2+1); for(int i=n+2,j=1;j<=n2;i++,j++) s1[i]=s2[j]; n+=1+n2; get_sa(); get_height(); // for(int i=1;i<=n;i++) printf("%d ",height[i]); int ans=0; for(int i=2;i<=n;i++){ if((sa[i]<pos && sa[i-1]>pos) || (sa[i]>pos && sa[i-1]<pos)){ ans=max(ans,height[i]); } } printf("%d\n",ans); return 0; }
扩展：求多个字符串的最长公共子串
例题4：hihocoder #1419 后缀数组四 重复旋律4
重复次数最多的连续子串
枚举长度 l ，枚举启示位置 p 为 l 的倍数，以 i - l + lcp(l, p) mod l 为分界线，右边的值因为LCP不够大，一定不能增加一个循环节。并且如果k(l, p - l + lcp(l, p) mod l)没有增加循环节的话，说明[p - l + lcp(l, p) mod l, p]这段中间匹配出错，左边的lcp也跟着雪崩，更不可能增加循环节了。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> #include<stack> #include<queue> using namespace std; typedef long long ll; const int maxn = 301000; int n,m,pos; int sa[maxn],rk[maxn],c[maxn],x[maxn],y[maxn],height[maxn]; char s1[maxn]; int st[maxn][22],lg[maxn]; void get_sa(){ for(int i=1;i<=n;i++) x[i]=s1[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 && s1[i+k]==s1[j+k]) k++; height[rk[i]]=k; } } void st_init(){ lg[1]=0; for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1; for(int i=1;i<=n;i++) st[i][0]=height[i]; for(int j=1;j<=lg[n];j++){ for(int i=1;i<=n;i++){ st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]); } } } int query(int x,int y){ int len=y-x+1; return min(st[x][lg[len]],st[y-(1<<lg[len])+1][lg[len]]); } int lcp(int x,int y){ int l=min(rk[x],rk[y])+1,r=max(rk[x],rk[y]); return query(l,r); } 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(){ m=1000; scanf("%s",s1+1); n=strlen(s1+1); get_sa(); get_height(); // for(int i=1;i<=n;i++) printf("%d ",height[i]); st_init(); int ans=0; for(int l=1;l<=n;l++){ // 调和级数 nlogn for(int i=1;i+l<=n;i+=l){ // 枚举倍数 int r=lcp(i,l+i); ans=max(ans,r/l+1); if(i-l+r%l>=0){ ans=max(ans,lcp(i-l+r%l,i+r%l)/l+1); } } } printf("%d\n",ans); return 0; }