问：既然有后缀自动机那么为什么还要后缀数组呢？
答：窝也不知道，好像是条哥要窝萌学的。
问：那学后缀数组有什么困难吗？
答：模板极其难背。。。
【简介】
然而窝懒得介绍（其实是窝不会介绍。。）
如果你想学，戳这
下面贴出模板：
void getsa(int *r,int *sa,int n,int m){
int *x=wa,*y=wb,j,p;
for (i=0;i<n;i++)wc[x[i]=r[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[x[i]]]=i;
for (j=1,p=1;p<n;j*=2,m=p){
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<n;i++)wd[i]=x[y[i]];
for (i=0;i<m;i++)wc[i]=0;
for (i=0;i<n;i++)wc[wd[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[wd[i]]]=y[i];
swap(x,y),p=1,x[sa[0]]=0;
for (i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void getheight(int *r,int *sa,int n){
int i,j,k=0;
for (i=1;i<=n;i++)rank[sa[i]]=i;
for (i=0;i<n;height[rank[i++]]=k){
if(k)k--;
j=sa[rank[i]-1];
while(r[i+k]==r[j+k])k++;
}
}
【例题】
poj2774 求两个串的最长公共子串，只要把两个串连起来求出height，然后找出一个height最大并且sa分别在两个串中的就行了。
poj3216 求出现至少k次的最长子串，等价于求max(lcp(i,i+k-1))。（谜之声：字符串hash大法好）
poj1743 题意极臭~~~首先差分，然后二分答案，那么只要求连续大于mid的height的sa的最大值与最小值之差是否大于mid就阔以了。
poj3294 求n个串中出现超过n/2次的最大长度子串。那么只要把n个串连起来，二分寻找满足条件的字符串。
poj1226 求最长串，使得该串或该串的回文串为n个串的子串。只要把n个串和其回文串连起来，然后就和前一题一样了。
poj3145 求长度不小于k的公共子串个数。计算A的后缀和B的后缀的LCP，如果>k，对答案的贡献是LCP-k+1。那么把两个串连起来然后通过height分组，扫描一遍，遇到B的后缀就统计一下前面A的后缀产生的贡献。由于LCP是求height的最小值，可以通过单调栈维护。
poj3581 把数组分成三分，翻转并重排，求最小字典序。只要逆过来，搞两遍sa求最小后缀就可以了，但是第二次需要重新接一遍，否则会出现反例。
【Codes】
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=200010;
char s1[M],s2[M];
int s[M],wa[M],wb[M],wc[M],wd[M],sa[M];
int rank[M],height[M];
int i,mx;
int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void getsa(int *r,int *sa,int n,int m){
int j,p,*x=wa,*y=wb;
for (i=0;i<n;i++)wc[x[i]=r[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[x[i]]]=i;
for (j=1,p=1;p<n;j*=2,m=p){
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<n;i++)wd[i]=x[y[i]];
for (i=0;i<m;i++)wc[i]=0;
for (i=0;i<n;i++)wc[wd[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[wd[i]]]=y[i];
swap(x,y),p=1,x[sa[0]]=0;
for (i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void getheight(int *r,int *sa,int n){
int i,j,k=0;
for (i=0;i<n;i++)rank[sa[i]]=i;
for (i=0;i<n;height[rank[i++]]=k){
if(k)k--;
if(!rank[i])continue;
j=sa[rank[i]-1];
while (r[i+k]==r[j+k])k++;
}
}
int main(){
scanf("%s",s1);
scanf("%s",s2);
int n=0,len=strlen(s1);
for (i=0;i<len;i++)s[n++]=s1[i]-'a'+1;
s[n++]=28;
len=strlen(s2);
for (i=0;i<len;i++)s[n++]=s2[i]-'a'+1;
for (i=0;i<=2*n+10;i++)wa[i]=wb[i]=-1;
getsa(s,sa,n,29);
getheight(s,sa,n);
len=strlen(s1);
for (i=0;i<=n;i++)
if (height[i]>mx){
if (sa[i-1]>=0&&sa[i-1]<len&&len<sa[i]||sa[i]>=0&&sa[i]<len&&len<sa[i-1])mx=height[i];
}
printf("%d\n",mx);
}
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
const int M=1000002;
const int inf=1000000007;
using namespace std;
int s[M],sa[M],wa[M],wb[M],wc[M],wd[M];
int rank[M],height[M];
int rmq[M/10][18];
int n,k,i,j,ans;
int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void getsa(int *r,int *sa,int n,int m){
int j,p,*x=wa,*y=wb;
for (i=0;i<n;i++)wc[x[i]=r[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[x[i]]]=i;
for (j=1,p=1;p<n;j*=2,m=p){
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<n;i++)wd[i]=x[y[i]];
for (i=0;i<m;i++)wc[i]=0;
for (i=0;i<n;i++)wc[wd[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[wd[i]]]=y[i];
swap(x,y);p=1;x[sa[0]]=0;
for (i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void getheight(int *r,int *sa,int n){
int i,j,k=0;
for (i=0;i<n;i++)rank[sa[i]]=i;
for (i=0;i<n;height[rank[i++]]=k){
if(k)k--;
if(!rank[i])continue;
j=sa[rank[i]-1];
while(r[i+k]==r[j+k])k++;
}
}
int main(){
scanf("%d%d",&n,&k);k--;
for (i=0;i<n;i++)scanf("%d",&s[i]),s[i]++;
for (i=0;i<2*n+10;i++)wa[i]=wb[i]=-1;
getsa(s,sa,n,M);
getheight(s,sa,n);
memset(rmq,inf,sizeof rmq);
for (i=0;i<n;i++)rmq[i][0]=height[i];
int len=log(n)/log(2)+1e-8;
for (j=1;j<=len;j++)
for (i=0;i<n;i++)
rmq[i][j]=min(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
len=log(k)/log(2)+1e-8;
for (i=0;i<=n-k;i++)ans=max(ans,min(rmq[i][len],rmq[i+k-(1<<len)][len]));
printf("%d\n",ans);
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100000;
int n,i,ans;
int s[M],sa[M],wa[M],wb[M],wc[M],wd[M];
int rank[M],height[M];
int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void getsa(int *r,int *sa,int n,int m){
int *x=wa,*y=wb,j,p;
memset(wc,0,sizeof wc);
for (i=0;i<n;i++)wc[x[i]=r[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[x[i]]]=i;
for (j=1,p=1;p<n;j*=2,m=p){
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<n;i++)wd[i]=x[y[i]];
for (i=0;i<m;i++)wc[i]=0;
for (i=0;i<n;i++)wc[wd[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[wd[i]]]=y[i];
swap(x,y),p=1,x[sa[0]]=0;
for (i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void getheight(int *r,int *sa,int n){
int i,j,k=0;
for (i=1;i<=n;i++)rank[sa[i]]=i;
for (i=0;i<n;height[rank[i++]]=k){
if(k)k--;
j=sa[rank[i]-1];
while(r[i+k]==r[j+k])k++;
}
}
int solve(int len){
int i=2,mx,Mx;
while (1){
while(i<=n&&height[i]<len)i++;
if (i>n)break;
mx=sa[i-1];Mx=sa[i-1];
while(i<=n&&height[i]>=len){
mx=max(mx,sa[i]);
Mx=min(Mx,sa[i]);
i++;
}
if(mx-Mx>=len)return 1;
}
return 0;
}
int main(){
scanf("%d",&n);
while (n){
for (i=0;i<n;i++)scanf("%d",&s[i]);
if (n<10){puts("0");scanf("%d",&n);continue;}
n--;
for (i=0;i<n;i++)s[i]=s[i+1]-s[i]+89;
s[n]=0;
for (i=0;i<2*n+10;i++)wa[i]=wb[i]=0;
getsa(s,sa,n+1,200);
getheight(s,sa,n);
int l=4,r=n-1>>1;
while(l+1<r){
int mid=l+r>>1;
if(solve(mid))l=mid;else r=mid;
}
if(solve(r))ans=r+1;else ans=l+1;
if(ans<5)ans=0;
printf("%d\n",ans);
scanf("%d",&n);
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=1000100;
char a[M];
int s[M],sa[M],wa[M],wb[M],wc[M],wd[M];
int rank[M],height[M],ans[M],vis[105],Len[105];
int n,i,j,flag,size,N;
int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void getsa(int *r,int *sa,int n,int m){
int *x=wa,*y=wb,j,p;
memset(wc,0,sizeof wc);
for (i=0;i<N;i++)wc[x[i]=r[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=N-1;i>=0;i--)sa[--wc[x[i]]]=i;
for (j=1,p=1;p<N;j*=2,m=p){
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<N;i++)wd[i]=x[y[i]];
for (i=0;i<m;i++)wc[i]=0;
for (i=0;i<N;i++)wc[wd[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=N-1;i>=0;i--)sa[--wc[wd[i]]]=y[i];
swap(x,y),p=1,x[sa[0]]=0;
for (i=1;i<N;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void getheight(int *r,int *sa,int n){
int i,j,k=0;
for (i=0;i<N;i++)rank[sa[i]]=i;
for (i=0;i<N;height[rank[i++]]=k){
if(k)k--;
if(!rank[i])continue;
j=sa[rank[i]-1];
while(r[i+k]==r[j+k])k++;
}
}
int solve(int x,int n,int k){
int i,j,cnt=size=0;
for (i=0;i<105;i++)vis[i]=1;
for (i=1;i<=N;i++){
if(height[i]>=x){
for (j=1;j<=k;j++){
if (sa[i]>Len[j-1]&&sa[i]<Len[j])cnt+=vis[j],vis[j]=0;
if (sa[i-1]>Len[j-1]&&sa[i-1]<Len[j])cnt+=vis[j],vis[j]=0;
}
}else{
if (cnt>k/2)ans[++size]=sa[i-1];
cnt=0;
for (int p=0;p<105;p++)vis[p]=1;
}
}
if (cnt>k/2)ans[++size]=sa[N];
if (size){ans[0]=size;return 1;}else return 0;
}
int main(){
flag=0;
while(scanf("%d",&n)&&n){
N=size=0;
for (i=1;i<=n;i++){
scanf("%s",a);
int len=strlen(a);
for (j=0;j<len;j++)s[N++]=a[j];
Len[++size]=N;
s[N++]='#'+i;
}
s[N-1]=0;
for (i=0;i<N+10;i++)wa[i]=wb[i]=-1;
getsa(s,sa,N,500);
getheight(s,sa,N-1);
int l=1,r=N;
while(l<=r){
int mid=l+r>>1;
if(solve(mid,N,n))l=mid+1;else r=mid-1;
}
if (flag)puts("");
flag=1;
if(l==1)puts("?");else{
for (i=1;i<=ans[0];i++){
for (j=ans[i];j<ans[i]+l-1;j++)printf("%c",s[j]);
puts("");
}
}
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100100;
char a[M];
int s[M],sa[M],wa[M],wb[M],wc[M],wd[M];
int rank[M],height[M],ans[M],vis[200],Len[200];
int n,i,j,flag,size,N;
int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void getsa(int *r,int *sa,int n,int m){
int *x=wa,*y=wb,j,p;
memset(wc,0,sizeof wc);
for (i=0;i<N;i++)wc[x[i]=r[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=N-1;i>=0;i--)sa[--wc[x[i]]]=i;
for (j=1,p=1;p<N;j*=2,m=p){
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<N;i++)wd[i]=x[y[i]];
for (i=0;i<m;i++)wc[i]=0;
for (i=0;i<N;i++)wc[wd[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=N-1;i>=0;i--)sa[--wc[wd[i]]]=y[i];
swap(x,y),p=1,x[sa[0]]=0;
for (i=1;i<N;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void getheight(int *r,int *sa,int n){
int i,j,k=0;
for (i=0;i<N;i++)rank[sa[i]]=i;
for (i=0;i<N;height[rank[i++]]=k){
if(k)k--;
if(!rank[i])continue;
j=sa[rank[i]-1];
while(r[i+k]==r[j+k])k++;
}
}
int solve(int x,int n,int k){
int i,j,cnt=size=0;
for (i=0;i<200;i++)vis[i]=1;
for (i=1;i<=N;i++){
if(height[i]>=x){
for (j=1;j<=k;j++){
if (sa[i]>Len[j-1]&&sa[i]<Len[j])cnt+=vis[j-1>>1],vis[j-1>>1]=0;
if (sa[i-1]>Len[j-1]&&sa[i-1]<Len[j])cnt+=vis[j-1>>1],vis[j-1>>1]=0;
}
}else{
if (cnt==k/2)size++;
cnt=0;
for (int p=0;p<200;p++)vis[p]=1;
}
}
if (cnt==k/2)size++;
if (size)return 1;else return 0;
}
int main(){
int cas;
scanf("%d",&cas);
while(cas--){
scanf("%d",&n);
N=size=0;
for (i=1;i<=n;i++){
scanf("%s",a);
int len=strlen(a);
for (j=0;j<len;j++)s[N++]=a[j];
Len[++size]=N;
s[N++]=200+i*2-1;
for (j=len-1;j>=0;j--)s[N++]=a[j];
Len[++size]=N;
s[N++]=200+i*2;
}
s[N-1]=0;
for (i=0;i<N+10;i++)wa[i]=wb[i]=-1;
getsa(s,sa,N,500);
getheight(s,sa,N-1);
int l=0,r=N;
while(l<r){
int mid=l+r+1>>1;
if(solve(mid,N,n*2))l=mid;else r=mid-1;
}
printf("%d\n",l);
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
const int M=600100;
char s1[M],s2[M];
int s[M],sa[M],wa[M],wb[M],wc[M],wd[M],rank[M],height[M];
int st[M][2];
int n,k,i;
ll top,tot;
int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void getsa(int *r,int *sa,int n,int m){
int *x=wa,*y=wb,j,p;
memset(wc,0,sizeof wc);
for (i=0;i<n;i++)wc[x[i]=r[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[x[i]]]=i;
for (j=1,p=1;p<n;j*=2,m=p){
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<n;i++)wd[i]=x[y[i]];
for (i=0;i<m;i++)wc[i]=0;
for (i=0;i<n;i++)wc[wd[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[wd[i]]]=y[i];
swap(x,y),p=1,x[sa[0]]=0;
for (i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void getheight(int *r,int *sa,int n){
int i,j,k=0;
for (i=1;i<=n;i++)rank[sa[i]]=i;
for (i=0;i<n;height[rank[i++]]=k){
if (k)k--;
j=sa[rank[i]-1];
while(r[i+k]==r[j+k])k++;
}
}
int main(){
while(scanf("%d",&k)&&k){
scanf("%s",s1);
scanf("%s",s2);
n=0;
int l1=strlen(s1),l2=strlen(s2);
for (i=0;i<l1;i++)s[n++]=s1[i];
s[n++]=34;
for (i=0;i<l2;i++)s[n++]=s2[i];
for (i=0;i<n+10;i++)wa[i]=wb[i]=-1;
n++;
s[n-1]=0;
getsa(s,sa,n,201);
getheight(s,sa,n-1);
ll sum=0;
tot=top=0;
for (i=1;i<n;i++){
if (height[i]<k)top=tot=0;
else{
int cnt=0;
if (sa[i-1]<l1)cnt++,tot+=height[i]-k+1;
while(top>0&&height[i]<=st[top-1][0]){
top--;
tot-=st[top][1]*(st[top][0]-height[i]);
cnt+=st[top][1];
}
st[top][0]=height[i];st[top++][1]=cnt;
if(sa[i]>l1)sum+=tot;
}
}
tot=top=0;
for (i=1;i<n;i++){
if (height[i]<k)top=tot=0;
else{
int cnt=0;
if (sa[i-1]>l1)cnt++,tot+=height[i]-k+1;
while (top>0&&height[i]<=st[top-1][0]){
top--;
tot-=st[top][1]*(st[top][0]-height[i]);
cnt+=st[top][1];
}
st[top][0]=height[i];st[top++][1]=cnt;
if(sa[i]<l1)sum+=tot;
}
}
printf("%I64d\n",sum);
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=200010;
int n,i;
int a[M],b[M],s[M];
int sa[M],wa[M],wb[M],wc[M],wd[M];
int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void getsa(int *r,int *sa,int n,int m){
int *x=wa,*y=wb,j,p;
memset(wc,0,sizeof wc);
for (i=0;i<n;i++)wc[x[i]=r[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[x[i]]]=i;
for (j=1,p=1;p<n;j*=2,m=p){
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<n;i++)wd[i]=x[y[i]];
for (i=0;i<m;i++)wc[i]=0;
for (i=0;i<n;i++)wc[wd[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[wd[i]]]=y[i];
swap(x,y),p=1,x[sa[0]]=0;
for (i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
int main(){
scanf("%d",&n);
for (i=0;i<n;i++)scanf("%d",&a[i]),b[i]=a[i];
sort(b,b+n);
int cnt=unique(b,b+n)-b;
for (i=0;i<n;i++)s[i]=lower_bound(b,b+cnt,a[n-i-1])-b+1;
for (i=0;i<n+10;i++)wa[i]=wb[i]=-1;
getsa(s,sa,n+1,cnt+1);
//for (i=0;i<=n;i++)printf("%d\n",sa[i]);
for (i=1;i<=n&&sa[i]<=1;i++);
int tmp=sa[i];
for (i=tmp;i<n;i++)printf("%d\n",a[n-i-1]);
for (i=0;i<tmp;i++)s[i+tmp]=s[i];
tmp*=2;
s[tmp]=0;
getsa(s,sa,tmp+1,cnt+1);
for (i=1;i<tmp&&(!sa[i]||sa[i]>=tmp/2);i++);
int tmp1=sa[i];
for (i=tmp1;i<tmp/2;i++)printf("%d\n",a[n-i-1]);
for (i=0;i<tmp1;i++)printf("%d\n",a[n-i-1]);
}
评论 (0)
