字符串后缀数组

倍增法，每次排2^j长度的段，转移就是双关键字排序就好啦！

求height可以利用height[rank[i]]>=height[rank[i-1]]-1的性质，当然证明考虑构造，并反证，假设在其中插入元素使性质不成立，推矛盾就可以了。

基本上是从网上抄来的模板啦，解释一下代码吧~

x在交换之前充当了rank的功能。

关于c的用处，来看计数排序的实现方法：

for(i=1;i<=n;i++){
scanf("%d",&a[i]);
++c[a[i]];
}
for(i=1;i<=m;i++)
c[i]+=c[i-1];
for(i=n;i;i--)
p[c[a[i]]--]=i;
for(i=1;i<=n;i++)
printf("%d",a[p[i]]);

y是按后半部分排序后前半部分开头序号，即x[y[i]+j]是单调的。

#include
#include
#include
using namespace std;
const int N=1e6+6;
char s[N];
int t1[N],t2[N],c[N];
int sa[N],rk[N],ht[N];
void gtsa(int n,int m){
int i,j,p=0,*x=t1,*y=t2;
for(i=1;i<=n;i++)
++c[x[i]=s[i]];
for(i=1;i<=m;i++)
c[i]+=c[i-1];
for(i=n;i;i--)
sa[c[x[i]]--]=i;
for(i=1;i<=m;i++)
c[i]=0;
for(j=1;j<=n&&p p=0;
for(i=n-j+1;i<=n;i++)
y[++p]=i;
for(i=1;i<=n;i++)
if(sa[i]>j)
y[++p]=sa[i]-j;
for(i=1;i<=n;i++)
++c[x[y[i]]];
for(i=1;i<=m;i++)
c[i]+=c[i-1];
for(i=n;i;i--)
sa[c[x[y[i]]]--]=y[i];
for(i=1;i<=m;i++)
c[i]=0;
swap(x,y);
p=1;
x[sa[1]]=1;
for(i=2;i<=n;i++)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j])?p:++p;
m=p;
}
for(i=1;i<=n;i++)
rk[sa[i]]=i;
p=0;
for(i=1;i<=n;i++){
j=sa[rk[i]-1];
if(p)--p;
while(s[i+p]==s[j+p])++p;
ht[rk[i]]=p;
}
}
int main()
{
scanf("%s",s+1);
int l=strlen(s+1);
gtsa(l,127);return 0;
}

 如果实在不能理解，可以先看一下这份冗长而低效的方法：

#include
#include
#include
using namespace std;
const int N=3e5+5;
char s[N];
int sa[N],rk[N],ht[N];
struct elm{
int x,r1,r2;
bool operator==(elm a)const{
return r1==a.r1&&r2==a.r2;
}
}p[N],q[N];
int sm[N];
void gtsa(int n,int m){
int i,j;
for(i=1;i<=n;i++)
p[i]=(elm){i,s[i],0};
for(i=1;i<=m;i++)
sm[i]=0;
for(i=1;i<=n;i++)
++sm[p[i].r2];
for(i=1;i<=m;i++)
sm[i]+=sm[i-1];
for(i=n;i;i--)
q[sm[p[i].r2]--]=p[i];
for(i=1;i<=n;i++)
p[i]=q[i];
for(i=1;i<=m;i++)
sm[i]=0;
for(i=1;i<=n;i++)
++sm[p[i].r1];
for(i=1;i<=m;i++)
sm[i]+=sm[i-1];
for(i=n;i;i--)
q[sm[p[i].r1]--]=p[i];
for(i=1;i<=n;i++)
p[i]=q[i];
m=1;
q[1].r1=m;
for(i=2;i<=n;i++)
q[i].r1=(p[i]==p[i-1]?m:++m);
for(i=1;i<=n;i++)
p[i]=q[i];
for(j=1;j<=n&&m for(i=1;i<=n;i++)
sm[i]=0;
for(i=1;i<=n;i++)
++sm[p[i].x];
for(i=1;i<=n;i++)
sm[i]+=sm[i-1];
for(i=n;i;i--)
q[sm[p[i].x]--]=p[i];
for(i=1;i<=n;i++)
p[i]=q[i];
for(i=n-j+1;i<=n;i++)
p[i].r2=0;
for(i=1;i<=n-j;i++)
p[i].r2=p[i+j].r1;
for(i=1;i<=m;i++)
sm[i]=0;
for(i=1;i<=n;i++)
++sm[p[i].r2];
for(i=1;i<=m;i++)
sm[i]+=sm[i-1];
for(i=n;i;i--)
q[sm[p[i].r2]--]=p[i];
for(i=1;i<=n;i++)
p[i]=q[i];
for(i=1;i<=m;i++)
sm[i]=0;
for(i=1;i<=n;i++)
++sm[p[i].r1];
for(i=1;i<=m;i++)
sm[i]+=sm[i-1];
for(i=n;i;i--)
q[sm[p[i].r1]--]=p[i];
for(i=1;i<=n;i++)
p[i]=q[i];
m=1;
q[1].r1=m;
for(i=2;i<=n;i++)
q[i].r1=(p[i]==p[i-1]?m:++m);
for(i=1;i<=n;i++)
p[i]=q[i];
}
for(i=1;i<=n;i++)
sa[i]=p[i].x,
rk[p[i].x]=i;
for(i=1,j=0;i<=n;i++){
if(j)--j;
while(s[i+j]==s[sa[rk[i]-1]+j])
++j;
ht[rk[i]]=j;
}
}
int main()
{
scanf("%s",s+1);
int l=strlen(s+1);
gtsa(l,127);
for(int i=1;i<=l;i++)
printf("%d ",sa[i]);
return 0;
}

更高效的算法请右转后缀自动机……