●之前学习过后缀数组的倍增算法，但也只是简单练了练倍增（O（n ㏒ n））。
●如今再次开始后缀，借助罗穗骞的论文《后缀数组——处理字符串的有力工具》，练习了论文里那十三个例题，学习了里面所包含的后缀数组处理字符串的应用。
●感觉收获不少，后缀倍增+后缀应用的代码能力提高了不少。
●于此发上各题方法的小总结，AC代码，以及除倍增算法外的时间复杂度，以此记录。
●后缀数组的应用
●一个字符串
○1、求字符串的字串个数。（SPOJ 694 SPOJ 705）
方法：一个串中不同子串的总数=∑(len-height[i]-sa[i])
复杂度： O（n）
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 50005
using namespace std;
char s[MAXN];
int sa[MAXN],rank[MAXN],height[MAXN];
int wa[MAXN],wy[MAXN],c[MAXN];
bool cmp(int *y,int i,int k,int n)
{
int aa=y[sa[i]],bb=y[sa[i-1]];
int cc=sa[i]+k<n?y[sa[i]+k]:0,dd=sa[i-1]+k<n?y[sa[i-1]+k]:0;
return aa==bb&&cc==dd;
}
void build(int n,int m)
{
int *x=wa,*y=wy,i;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[i]=s[i]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
for(int k=1;k<=n;k<<=1)
{
int p=0;
for(i=n-k;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[y[i]]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
m=2; swap(x,y); x[sa[0]]=1;
for(i=1;i<n;i++)
x[sa[i]]=cmp(y,i,k,n)?m-1:m++;
if(m>n) break;
}
for(i=0;i<n;i++) rank[sa[i]]=i;
int h=0;
for(i=0;i<n;i++)
{
if(h) h--;
if(rank[i]==0) continue;
int j=sa[rank[i]-1];
while(s[i+h]==s[j+h]) h++;
height[rank[i]]=h;
}
}
long long solve(int n)
{
long long ans=0;
for(int i=0;i<n;i++) ans+=n-sa[i]-height[i];
return ans;
}
int main()
{
int k,n;scanf("%d",&k);
while(k--)
{
scanf("%s",s);
n=strlen(s);
build(n,300);
long long ans=solve(n);
printf("%I64d
",ans);
}
return 0;
}
○2、询问后缀LCP
方法：height[ ]构建ST表，然后RMQ
复杂度：预处理 O（n ㏒ n） 询问 O（1）
○3、可重叠最长重复子串
方法：max(height[ ])
复杂度：O（n）
○4、不可重叠最长重复子串（POJ 1743）
方法：二分+height 分组
复杂度：O（n ㏒ n）
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 20005
using namespace std;
int s[MAXN];
int sa[MAXN],rank[MAXN],height[MAXN];
int wa[MAXN],wy[MAXN],c[MAXN];
int mi=0x3f3f3f3f;
bool cmp(int *y,int i,int k,int n)
{
int aa=y[sa[i]],bb=y[sa[i-1]];
int cc=sa[i]+k<n?y[sa[i]+k]:0,dd=sa[i-1]+k<n?y[sa[i-1]+k]:0;
return aa==bb&&cc==dd;
}
void build(int m,int n)
{
int *x=wa,*y=wy,i;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[i]=s[i]-mi+1]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
for(int k=1;k<=n;k<<=1)
{
int p=0;
for(i=n-k;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[y[i]]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
m=1; swap(x,y); x[sa[0]]=0;
for(i=1;i<n;i++)
x[sa[i]]=cmp(y,i,k,n)?m-1:m++;
if(m>=n) break;
}
for(i=0;i<n;i++) rank[sa[i]]=i;
int h=0;
for(i=0;i<n;i++)
{
if(h) h--;
if(rank[i]==0) continue;
int j=sa[rank[i]-1];
while(s[i+h]==s[j+h]) h++;
height[rank[i]]=h;
}
}
bool check(int x,int n)
{
int ml=0x3f3f3f3f,mr=-0x3f3f3f3f;
for(int i=1;i<n+1;i++)
{
if(i<=n&&height[i]>=x) ml=min(ml,min(sa[i-1],sa[i])),mr=max(mr,max(sa[i-1],sa[i]));
else
{
if(mr-ml>=x) return 1;
ml=0x3f3f3f3f; mr=-0x3f3f3f3f;
}
}
return 0;
}
int solve(int n)
{
int l=4,r=n/2-1,ans=0,mid;
while(l<=r)
{
mid=(l+r)/2;
if(check(mid,n-1)) ans=mid,l=mid+1;
else r=mid-1;
}
return ans;
}
int main()
{
while(1)
{
int x,y,n;
scanf("%d
",&n);
if(n==0) break;
scanf("%d",&y);
for(int i=1;i<n;i++)
{
scanf("%d",&x);
s[i-1]=x-y;
y=x;
mi=min(mi,s[i-1]);
}
if(n<10) {printf("0
"); continue;}
build(200,n-1);
int ans=solve(n);
printf("%d
",ans+1);
}
return 0;
}
○5、可重叠至少出现k次的最长重复子串（POJ 3261）
方法：二分+height 分组
复杂度：O（n ㏒ n）
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 20005
using namespace std;
int s[MAXN],xx[MAXN];
int sa[MAXN],rank[MAXN],height[MAXN];
int wa[MAXN],wy[MAXN],c[MAXN];
bool cmp(int *y,int i,int k,int n)
{
int aa=y[sa[i]],bb=y[sa[i-1]];
int cc=sa[i]+k<n?y[sa[i]+k]:0,dd=sa[i-1]+k<n?y[sa[i-1]+k]:0;
return aa==bb&&cc==dd;
}
void build(int n,int m)
{
int *x=wa,*y=wy,i;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[i]=s[i]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
for(int k=1;k<=n;k<<=1)
{
int p=0;
for(i=n-k;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[y[i]]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
m=2; swap(x,y); x[sa[0]]=1;
for(i=1;i<n;i++)
x[sa[i]]=cmp(y,i,k,n)?m-1:m++;
if(m>n) break;
}
for(i=0;i<n;i++) rank[sa[i]]=i;
int h=0;
for(i=0;i<n;i++)
{
if(h) h--;
if(rank[i]==0) continue;
int j=sa[rank[i]-1];
while(s[i+h]==s[j+h]) h++;
height[rank[i]]=h;
}
}
bool check(int n,int x,int k)
{
int cnt=1;
for(int i=1;i<=n;i++)
{
if(i<n&&height[i]>=x) cnt++;
else
{
if(cnt>=k) return 1;
cnt=1;
}
}
return 0;
}
int solve(int n,int k)
{
int l=1,r=n-k+1,ans=0,mid;
while(l<=r)
{
mid=(l+r)/2;
if(check(n,mid,k)) ans=mid,l=mid+1;
else r=mid-1;
}
return ans;
}
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++) scanf("%d",&s[i]),xx[i]=s[i];
sort(xx,xx+n); int d=unique(xx,xx+n)-xx;
for(int i=0;i<n;i++) s[i]=lower_bound(xx,xx+d,s[i])-xx+1;
build(n,d+1);
int ans=solve(n,k);
printf("%d",ans);
return 0;
}
○6、连续重复子串（找原串的最短循环子串（循环节））（POJ 2406）
方法：
后缀数组：穷举循环子串的长度L，判断RMQ（suffix（0），suffix（L））是否等于n-L。
复杂度：O（n ㏒ n）
但对于本题，数据范围过大，连倍增算法可能都不太跑得动。
我看网上有用DC3的代码，有100多行。
但感觉其实KMP才是王道，只有19行。
代码（KMP的）：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int next[1000005],tot;
char s[1000005];
int main()
{
int k,j,n; next[0]=-1;
while(1)
{
scanf("%s",s); if(s[0]=='.') break;
n=strlen(s); k=-1; j=0;
while(j<n) if(k==-1||s[k]==s[j]) k++,j++,next[j]=k;else k=next[k];
if(!(n%(n-next[n]))) printf("%d
",n/(n-next[n]));
else printf("1
");
}
return 0;
}
○7、重复最多的连续重复子串（POJ 3693 SPOJ 687）
方法：论文里的说，穷举L，i，RMQ（suffix（iL），suffix（iL+L））+”错位“判断
但这个”错位“判断的代码实现真的令我绝望，况且POJ上还有求输出字典序最小的那个串。。。最后我还是学习的网上一个大佬的方法，但复杂度我不知如何证明。
代码（POJ的，SPOJ的”简单版“我WA了，还不知道错在哪里）：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define MAXN 100005
using namespace std;
char s[MAXN];
int sa[MAXN],rank[MAXN],height[MAXN];
int wa[MAXN],wb[MAXN],c[MAXN];
int st[MAXN][15],a[MAXN];
int al,ap,ans,cnt;
bool cmp(int *y,int i,int k,int n)
{
int aa=y[sa[i]],bb=y[sa[i-1]];
int cc=sa[i]+k<n?y[sa[i]+k]:0,dd=sa[i-1]+k<n?y[sa[i-1]+k]:0;
return aa==bb&&cc==dd;
}
void build(int n,int m)
{
int *x=wa,*y=wb,i;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[i]=s[i]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
for(int k=1;k<=n;k<<=1)
{
int p=0;
for(i=n-k;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[y[i]]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
m=2; swap(x,y); x[sa[0]]=1;
for(i=1;i<n;i++)
x[sa[i]]=cmp(y,i,k,n)?m-1:m++;
if(m>n) break;
}
for(i=0;i<n;i++) rank[sa[i]]=i;
int h=0;
for(i=0;i<n;i++)
{
if(h) h--;
if(rank[i]==0) {height[rank[i]]=0;continue;}
int j=sa[rank[i]-1];
while(s[i+h]==s[j+h]) h++;
height[rank[i]]=h;
}
}
void pre_ST(int n)
{
for(int i=1;i<n;i++) st[i][1]=height[i];
for(int j=2;(1<<j)<n;j++)
for(int i=(1<<j);i<n;i++)
st[i][j]=min(st[i-(1<<(j-1))+1][1],min(st[i-(1<<(j-1))][j-1],st[i][j-1]));
}
int rmq(int p1,int p2,int n)
{
if(p1>=n||p2>=n) return 0;
p1=rank[p1]; p2=rank[p2];
if(p1>p2) swap(p1,p2);
int k=log2(p2-p1+1);
return min(st[p1+(1<<k)-1][k],st[p2][k]);
}
void solve(int n)
{
int now,k,p; ans=0,cnt=0;
for(int l=1;l<=n/2;l++)
for(int i=0;i+l<n;i+=l)
{
k=rmq(i,i+l,n);
now=k/l+1;
p=i-(l-k%l);
if(p>=0&&k%l!=0&&rmq(p,p+l,n)>=k) now++;
if(now>ans) cnt=0,a[++cnt]=l,ans=now;
else if(now==ans) a[++cnt]=l;
}
ap=0; al=0;
for(int i=0;i<n;i++) //根据排名枚举，保证字典序最小
for(int j=1;j<=cnt;j++)
{
k=rmq(sa[i],sa[i]+a[j],n);
if(k>=(ans-1)*a[j])
{
ap=sa[i];
al=ans*a[j];
i=n;
break;
}
}
}
int main()
{
int n,cas=1;
while(1)
{
scanf(" %s",s); if(s[0]=='#') break;
printf("Case %d: ",cas++);
n=strlen(s);
build(n,300);
pre_ST(n);
solve(n);
for(int i=ap;i<ap+al;i++) printf("%c",s[i]);
printf("
");
}
return 0;
}
○8、最长回文串（ural 1297）
方法：原串和反转串拼凑（中间用未出现过的字符连接），枚举回文中心，RMQ对应位置的两个后缀的LCP，并分奇偶串讨论。
复杂度：O（n ㏒ n）
代码：
#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 20005
using namespace std;
char s[MAXN];
int sa[MAXN],rank[MAXN],height[MAXN];
int wa[MAXN],wy[MAXN],c[MAXN];
int st[MAXN][12];
int ans,ap;
bool cmp(int *y,int i,int k,int n)
{
int aa=y[sa[i]],bb=y[sa[i-1]];
int cc=sa[i]+k<n?y[sa[i]+k]:0,dd=sa[i-1]+k<n?y[sa[i-1]+k]:0;
return aa==bb&&cc==dd;
}
void build(int n,int m)
{
int *x=wa,*y=wy,i;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[i]=s[i]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
for(int k=1;k<=n;k<<=1)
{
int p=0;
for(i=n-k;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[y[i]]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
m=2; swap(x,y); x[sa[0]]=1;
for(i=1;i<n;i++)
x[sa[i]]=cmp(y,i,k,n)?m-1:m++;
if(m>n) break;
}
for(i=0;i<n;i++) rank[sa[i]]=i;
int h=0;
for(i=0;i<n;i++)
{
if(h) h--;
if(rank[i]==0) continue;
int j=sa[rank[i]-1];
while(s[i+h]==s[j+h]) h++;
height[rank[i]]=h;
}
}
void pre_ST(int n)
{
for(int i=1;i<n;i++) st[i][1]=height[i];
for(int j=2;(1<<j)<n;j++)
for(int i=(1<<j);i<n;i++)
st[i][j]=min(st[i-(1<<(j-1))+1][1],min(st[i-(1<<(j-1))][j-1],st[i][j-1]));
}
int rmq(int p1,int p2)
{
p1=rank[p1]; p2=rank[p2];
if(p1>p2) swap(p1,p2);
int k=log2(p2-p1+1);
return min(st[p1+(1<<k)-1][k],st[p2][k]);
}
void solve(int n)
{
int p1,p2,l;
ans=0,ap=-1;
for(p1=0;p1<n/2;p1++)
{
p2=n-1-p1;
//奇
l=rmq(p1,p2);
if(ans<(l-1)*2+1)
{
ans=(l-1)*2+1;
ap=p1-l+1;
}
//偶
l=rmq(p1,p2+1);
if(ans<l*2)
{
ans=l*2;
ap=p1-l;
}
}
}
int main()
{
int n,l;
scanf("%s",s);
l=strlen(s);s[l]=1;
n=2*l+1;
for(int i=0;i<l;i++) s[n-1-i]=s[i];
build(n,300);
pre_ST(n);
solve(n);
if(ans) for(int i=ap;i<=ap+ans-1;i++) printf("%c",s[i]);
puts("");
return 0;
}
●两个字符串
○9、最长公共子串（POJ 2774）
方法：拼凑+max（height[ ]），且height[i]对应的sa[i]和sa[i-1]位于不同串。
复杂度：O（n）
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 200005
using namespace std;
char s[MAXN];
int sa[MAXN],rank[MAXN],height[MAXN];
int wa[MAXN],wy[MAXN],c[MAXN];
bool cmp(int *y,int i,int k,int n)
{
int aa=y[sa[i]],bb=y[sa[i-1]];
int cc=sa[i]+k<n?y[sa[i]+k]:0,dd=sa[i-1]+k<n?y[sa[i-1]+k]:0;
return aa==bb&&cc==dd;
}
void build(int n,int m)
{
int *x=wa,*y=wy,i;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[i]=s[i]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
for(int k=1;k<=n;k<<=1)
{
int p=0;
for(i=n-k;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[y[i]]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
m=2; swap(x,y); x[sa[0]]=1;
for(i=1;i<n;i++)
x[sa[i]]=cmp(y,i,k,n)?m-1:m++;
if(m>n) break;
}
for(i=0;i<n;i++) rank[sa[i]]=i;
int h=0;
for(i=0;i<n;i++)
{
if(h) h--;
if(rank[i]==0) continue;
int j=sa[rank[i]-1];
while(s[i+h]==s[j+h]) h++;
height[rank[i]]=h;
}
}
int solve(int n,int l)
{
int ans=0;
for(int i=2;i<n;i++)
if((sa[i-1]<l)^(sa[i]<l)) ans=max(ans,height[i]);
return ans;
}
int main()
{
int n,l;
scanf("%s",s);
l=strlen(s); s[l]=1;
scanf("%s",s+l+1);
n=strlen(s);
build(n,300);
int ans=solve(n,l);
printf("%d",ans);
return 0;
}
○10、长度不小于k的公共子串的个（对）数（有点不好理解题意）（POJ 3415）
方法：拼凑+按k对height[]进行分组+单调栈维护答案贡献
复杂度：O（n）
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 200002
using namespace std;
char s[MAXN];
int sa[MAXN],rank[MAXN],height[MAXN];
int wa[MAXN],wy[MAXN],c[MAXN];
int a[MAXN],f[MAXN],b[MAXN];
int n;
long long ans,tmp;
bool cmp(int *y,int i,int k,int n)
{
int aa=y[sa[i]],bb=y[sa[i-1]];
int cc=sa[i]+k<n?y[sa[i]+k]:0,dd=sa[i-1]+k<n?y[sa[i-1]+k]:0;
return aa==bb&&cc==dd;
}
void build()
{
int *x=wa,*y=wy,m=300,i;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[i]=s[i]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
for(int k=1;k<n;k<<=1)
{
int p=0;
for(i=n-k;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[y[i]]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
m=2; swap(x,y); x[sa[0]]=1;
for(i=1;i<n;i++)
x[sa[i]]=cmp(y,i,k,n)?m-1:m++;
if(m>n) break;
}
for(i=0;i<n;i++) rank[sa[i]]=i;
int h=0;
for(i=0;i<n;i++)
{
if(h) h--;
if(rank[i]==0) continue;
int j=sa[rank[i]-1];
while(s[i+h]==s[j+h]) h++;
height[rank[i]]=h;
}
}
int main()
{
int k,l;
while(1)
{
scanf("%d",&k);
if(!k) break;
scanf("%s",s); l=strlen(s);
s[l]=1;
scanf("%s",s+l+1);
n=strlen(s);
build();
for(int i=1;i<n;i++)
{
f[i]=sa[i]<l;
height[i]-=k-1;
if(height[i]<0) height[i]=0;
}
a[0]=-1;
height[n]=0;
ans=0;
int p;
for(int t=0;t<=1;t++)
{
tmp=0;
p=0;
for(int i=1;i<n;i++)
{
if(f[i]!=t) ans+=tmp;
p++;
a[p]=height[i+1];
b[p]=f[i]==t;
tmp+=(long long)a[p]*b[p];
while(a[p-1]>=a[p])
{
tmp-=(long long)(a[p-1]-a[p])*b[p-1];
a[p-1]=a[p];
b[p-1]+=b[p];
p--;
}
}
}
printf("%I64d
",ans);
//cout<<ans<<endl;
}
return 0;
}
●多个字符串（这三个都比较套路了，方法大同小异）
○11、出现在不少于k个字符串中（POJ 3294）
方法：拼凑各串+二分+height 分组
复杂度：O（n ㏒ n）
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 110000
using namespace std;
char ch;
int s[MAXN],r[MAXN],a[MAXN];
int sa[MAXN],rank[MAXN],height[MAXN];
int wa[MAXN],wy[MAXN],c[MAXN];
int vis[105];
int t,cnt,tot,mi;
bool cmp(int *y,int i,int k,int n)
{
int aa=y[sa[i]],bb=y[sa[i-1]];
int cc=sa[i]+k<n?y[sa[i]+k]:0,dd=sa[i-1]+k<n?y[sa[i-1]+k]:0;
return aa==bb&&cc==dd;
}
void build(int n,int m)
{
int *x=wa,*y=wy,i;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[i]=s[i]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
for(int k=1;k<=n;k<<=1)
{
int p=0;
for(i=n-k;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[y[i]]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
m=1; swap(x,y); x[sa[0]]=0;
for(i=1;i<n;i++)
x[sa[i]]=cmp(y,i,k,n)?m-1:m++;
if(m>=n) break;
}
for(i=0;i<n;i++) rank[sa[i]]=i;
int h=0;
for(i=0;i<n;i++)
{
if(h) h--;
if(rank[i]==0) continue;
int j=sa[rank[i]-1];
while(s[i+h]==s[j+h]) h++;
height[rank[i]]=h;
}
}
bool check(int x,int n,int k)
{
t++; cnt=1; vis[r[sa[0]]]=t; tot=0; bool fg=0;
for(int i=1;i<=n;i++)
{
if(i<n&&height[i]>=x)
{
if(r[sa[i]]&&vis[r[sa[i]]]!=t) vis[r[sa[i]]]=t,cnt++;
}
else
{
if(cnt>=k) a[++tot]=sa[i-1],fg=1;
cnt=0;
t++;
if(r[sa[i]]&&vis[r[sa[i]]]!=t) vis[r[sa[i]]]=t,cnt++;
}
}
return fg;
}
void solve(int n,int k)
{
int l=1,r=mi,mid,ans=-1,ant;
while(l<=r)
{
mid=(l+r)/2;
if(check(mid,n,k)) ans=mid,ant=tot,l=mid+1;
else r=mid-1;
}
if(ans==-1){printf("?");return;}
for(int i=1;i<=ant;i++)
{
for(int j=a[i];j<a[i]+ans;j++) printf("%c",s[j]+'A');
if(i!=ant) printf("
");
}
}
int main()
{
int n,k,l; bool fg=0;
while(1)
{
scanf("%d",&k); char ss[1005]; mi=0x3f3f3f3f; n=0;
if(!k) break;
if(fg) printf("
");
if(!fg) fg=1;
for(int i=1;i<=k;i++)
{
scanf("%s",ss); l=strlen(ss); mi=min(mi,l);
for(int j=0;j<l;j++) s[n+j]=ss[j]-'A',r[n+j]=i;
n+=l; s[n]=i+200; r[n]=0; n++;
}
build(n,350);
solve(n,k/2+1);
}
return 0;
}
○12、在每个字符串中不重复出现两次的最长子串（SPOJ 220）
方法：拼凑各串+二分+height 分组
复杂度：O（n ㏒ n）
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 110000
using namespace std;
char ch;
int s[MAXN],r[MAXN],a[MAXN];
int sa[MAXN],rank[MAXN],height[MAXN];
int wa[MAXN],wy[MAXN],c[MAXN];
int vis[2][15];
int t,cnt,tot,mi;
bool cmp(int *y,int i,int k,int n)
{
int aa=y[sa[i]],bb=y[sa[i-1]];
int cc=sa[i]+k<n?y[sa[i]+k]:0,dd=sa[i-1]+k<n?y[sa[i-1]+k]:0;
return aa==bb&&cc==dd;
}
void build(int n,int m)
{
int *x=wa,*y=wy,i;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[i]=s[i]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
for(int k=1;k<=n;k<<=1)
{
int p=0;
for(i=n-k;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[y[i]]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
m=1; swap(x,y); x[sa[0]]=0;
for(i=1;i<n;i++)
x[sa[i]]=cmp(y,i,k,n)?m-1:m++;
if(m>=n) break;
}
for(i=0;i<n;i++) rank[sa[i]]=i;
int h=0;
for(i=0;i<n;i++)
{
if(h) h--;
if(rank[i]==0) continue;
int j=sa[rank[i]-1];
while(s[i+h]==s[j+h]) h++;
height[rank[i]]=h;
}
}
bool check(int x,int n,int k)
{
memset(vis[0],0x3f,sizeof(vis[0]));
memset(vis[1],-1,sizeof(vis[1]));
bool fg=0;
vis[0][r[sa[0]]]=min(vis[0][r[sa[0]]],sa[0]);
vis[1][r[sa[0]]]=max(vis[1][r[sa[0]]],sa[0]);
for(int i=1;i<=n;i++)
{
if(i<n&&height[i]>=x)
{
vis[0][r[sa[i]]]=min(vis[0][r[sa[i]]],sa[i]);
vis[1][r[sa[i]]]=max(vis[1][r[sa[i]]],sa[i]);
}
else
{
fg=1;
for(int j=1;j<=k;j++)
if(vis[1][j]-vis[0][j]<x) {fg=0;break;}
if(fg) return 1;
memset(vis[0],0x3f,sizeof(vis[0]));
memset(vis[1],-1,sizeof(vis[1]));
vis[0][r[sa[i]]]=min(vis[0][r[sa[i]]],sa[i]);
vis[1][r[sa[i]]]=max(vis[1][r[sa[i]]],sa[i]);
}
}
return 0;
}
void solve(int n,int k)
{
int l=1,r=mi/2,mid,ans=0;
while(l<=r)
{
mid=(l+r)/2;
if(check(mid,n,k)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d
",ans);
}
void gs(char *ss)
{
int p=0; ch=getchar();
while(ch<'a'||ch>'z') ch=getchar();
while('a'<=ch&&ch<='z') ss[p++]=ch,ch=getchar();
ss[p]=0;
}
int main()
{
int n,k,l,T; scanf("%d",&T);
while(T--)
{
scanf("%d",&k); char ss[10005]; mi=0x3f3f3f3f; n=0;
for(int i=1;i<=k;i++)
{
gs(ss),l=strlen(ss); mi=min(mi,l);
for(int j=0;j<l;j++) s[n+j]=ss[j]-'a',r[n+j]=i;
n+=l; s[n]=i+200; r[n]=0; n++;
}
build(n,350);
solve(n,k);
}
return 0;
}
○13、出现在每个字符串或原串反转串中的最长子串（POJ 1226）
方法：拼凑各串及其反转串+二分+height 分组
复杂度：O（n ㏒ n）
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 30000
using namespace std;
int s[MAXN],r[MAXN],a[MAXN];
int sa[MAXN],rank[MAXN],height[MAXN];
int wa[MAXN],wy[MAXN],c[MAXN];
bool vis[105];
int t,cnt,tot,mi;char ch;
bool cmp(int *y,int i,int k,int n)
{
int aa=y[sa[i]],bb=y[sa[i-1]];
int cc=sa[i]+k<n?y[sa[i]+k]:0,dd=sa[i-1]+k<n?y[sa[i-1]+k]:0;
return aa==bb&&cc==dd;
}
void build(int n,int m)
{
int *x=wa,*y=wy,i;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[i]=s[i]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
for(int k=1;k<=n;k<<=1)
{
int p=0;
for(i=n-k;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[y[i]]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
m=1; swap(x,y); x[sa[0]]=0;
for(i=1;i<n;i++)
x[sa[i]]=cmp(y,i,k,n)?m-1:m++;
if(m>=n) break;
}
for(i=0;i<n;i++) rank[sa[i]]=i;
int h=0;
for(i=0;i<n;i++)
{
if(h) h--;
if(rank[i]==0) continue;
int j=sa[rank[i]-1];
while(s[i+h]==s[j+h]) h++;
height[rank[i]]=h;
}
}
bool check(int x,int n,int k)
{
memset(vis,0,sizeof(vis));
bool fg=0;
for(int i=1;i<=n;i++)
{
if(i<n&&height[i]>=x)
{
vis[r[sa[i]]]=1;
}
else
{
fg=1;
for(int j=1;j<=k;j++)
if(!vis[j]) {fg=0;break;}
if(fg) return 1;
memset(vis,0,sizeof(vis));
vis[r[sa[i]]]=1;
}
}
return 0;
}
void solve(int n,int k)
{
int l=1,r=mi,mid,ans=0;
while(l<=r)
{
mid=(l+r)/2;
if(check(mid,n,k)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d
",ans);
}
int main()
{
int n,k,l,T,o; scanf("%d",&T);
while(T--)
{
scanf("%d",&k); char ss[105]; mi=0x3f3f3f3f; n=0,o=200;
for(int i=1;i<=k;i++)
{
scanf("%s",ss);l=strlen(ss); mi=min(mi,l);
for(int j=0;j<l;j++) s[n+j]=ss[j],r[n+j]=i;
n+=l; s[n]=o++; r[n]=0; n++;
for(int j=0;j<l;j++) s[n+j]=ss[l-j-1],r[n+j]=i;
n+=l; s[n]=o++; r[n]=0; n++;
}
build(n,350);
solve(n,k);
}
return 0;
}