简单介绍：
在字符串处理当中，后缀树和后缀数组都是非常有力的工具。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。可以说，在信息学竞赛中后缀数组比后缀树要更为实用。
作用：
后缀数组能快速比较两个后缀的字典序大小，它还能求多个字符串两两的LCP。
实现：
后缀数组一般是用倍增做的，总的时间复杂度是:,空间复杂度是:
排序是用基数排序来实现的。
代码：
#include
using namespace std;
const int N=1e6+35;
int n,p,c[N],a[N],sa[N],x[N],y[N];
//sa[i]表示排名为i的后缀的起点
//c[]用于基数排序
char s[N];
void SA(int n,int m)
{
for(int i=1;i<=m;i++)c[i]=0;//清空鸡排数组
for(int i=1;i<=n;i++)c[x[i]=a[i]]++;
for(int i=1;i<=m;i++)c[i]+=c[i-1];//前缀和
for(int i=n;i>0;i--)sa[c[x[i]]--]=i;//第一轮的sa数组
for(int i=1;i;i=i*2)//倍增
{
p=0;
for(int j=n-i+1;j<=n;j++)y[++p]=j;//倍增个数不够，要补0
for(int j=1;j<=n;j++)
if(sa[j]>i)y[++p]=sa[j]-i;
for(int j=1;j<=m;j++)c[j]=0;//清空鸡排数组
for(int j=1;j<=n;j++)c[x[y[j]]]++;
for(int j=1;j<=m;j++)c[j]+=c[j-1];
for(int j=n;j>0;j--)sa[c[x[y[j]]]--]=y[j];
swap(x,y);//注意
x[sa[1]]=1;
p=2;//注意
for(int j=2;j<=n;j++)
{
if(y[sa[j]]==y[sa[j-1]]&&y[sa[j]+i]==y[sa[j-1]+i])x[sa[j]]=p-1;//相同
else x[sa[j]]=p++;//不相同
}
if(p>n)return;//全部不相同
m=p;//小优化
}
}
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
for(int i=1;i<=n;i++)a[i]=s[i];
SA(n,233);
for(int i=1;i<=n;i++)printf("%d ",sa[i]);
return 0;
} 题目：1031: [JSOI2007]字符加密Cipher
作用2：
后缀数组求多个字符串两两的LCP。
这是怎么做的呢？思想是把多个字符串拼成一个串，两个串之间用“#”隔开。
height数组定义：定义height[i]=suffix(sa[i-1])和suffix(sa[i])的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀。
对于j和k，不妨设rank[j]<rank[k],则有以下性质：
suffix(j)和suffix(k)的最长公共前缀为:
height[rank[j]+1], height[rank[j]+2], height[rank[j]+3], …, height[rank[k]]中的最小值。
所以这个可以用倍增即st表来完成。
题目：[P1117 [NOI2016]优秀的拆分
代码：
#include
using namespace std;
const int N=3e5+5;
char a[N];
int T,n,p,Log[N],f[N],g[N];
struct node{
int sa[N],rk[N],height[N],c[N],x[N],y[N],st[N][25];
void SA(int n,int m)
{
memset(sa,0,sizeof(sa));
memset(rk,0,sizeof(rk));
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
for(int i=1;i<=m;i++)c[i]=0;
for(int i=1;i<=n;i++)c[x[i]=a[i]]++;
for(int i=1;i<=m;i++)c[i]+=c[i-1];
for(int i=n;i;i--)sa[c[x[i]]--]=i;
for(int i=1;i;i=i*2)
{
p=0;
for(int j=n-i+1;j<=n;j++)y[++p]=j;
for(int j=1;j<=n;j++)
if(sa[j]>i)y[++p]=sa[j]-i;
for(int j=1;j<=m;j++)c[j]=0;
for(int j=1;j<=n;j++)c[x[y[j]]]++;
for(int j=1;j<=m;j++)c[j]+=c[j-1];
for(int j=n;j;j--)sa[c[x[y[j]]]--]=y[j];
swap(x,y);
x[sa[1]]=1;
p=2;
for(int j=2;j<=n;j++)
{
if(y[sa[j]]==y[sa[j-1]]&&y[sa[j]+i]==y[sa[j-1]+i])x[sa[j]]=p-1;
else x[sa[j]]=p++;
}
if(p>n)return;
m=p;
}
}
void Height()//求出height数组，height[i]=lcp(sa[i-1],sa[i])
{
memset(height,0,sizeof(height));
int k=0;
for(int i=1;i<=n;i++)rk[sa[i]]=i;//rk[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;
}
}
void ST()//倍增求min{height[]}
{
memset(st,0x3f,sizeof(st));
for(int i=1;i<=n;i++)st[i][0]=height[i];
for(int i=1;i<=15;i++)
for(int j=1;j<=n;j++)
st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
int query(int l,int r)
{
int L=l,R=r;
l=min(rk[L],rk[R])+1;
r=max(rk[L],rk[R]);
int t=Log[r-l+1];
return min(st[l][t],st[r-(1<<t)+1][t]);
}
}A,B;
void work()
{
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
scanf("%s",a+1);
n=strlen(a+1);
A.SA(n,122);
A.Height();
A.ST();
reverse(&a[1],&a[n+1]);
B.SA(n,122);
B.Height();
B.ST();
for(int len=1;len<=n/2;len++)
{
for(int i=len,j=i+len;j<=n;i+=len,j+=len)
{
int lcp=min(A.query(i,j),len),lcs=min(B.query(n-i+2,n-j+2),len-1);
int t=lcp+lcs-len+1;
if(lcp+lcs>=len)
{
g[i-lcs]++;g[i-lcs+t]--;
f[j+lcp-t]++;f[j+lcp]--;
}
}
}
for(int i=1;i<=n;i++)f[i]+=f[i-1],g[i]+=g[i-1];
long long ans=0;
for(int i=1;i<n;i++)ans+=1ll*f[i]*g[i+1];
printf("%lld\n",ans);
}
int main()
{
Log[0]=-1;
for(int i=1;i>1]+1;
scanf("%d",&T);
while(T--)work();
return 0;
} 题目:P4341 [BJWC2010]外星联络
代码：
#include
using namespace std;
const int N=1e6+5;
int n,a[N],x[N],y[N],c[N],sa[N],rk[N],height[N];
char s[N];
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
#define gc getchar
inline int read()
{
int ret=0,f=0;char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){ret=ret*10+c-48;c=gc();}
if(f)return -ret;return ret;
}
void SA(int n,int m)
{
int p;
for(int i=1;i<=m;i++)c[i]=0;
for(int i=1;i<=n;i++)c[x[i]=a[i]]++;
for(int i=1;i<=m;i++)c[i]+=c[i-1];
for(int i=n;i;i--)sa[c[x[i]]--]=i;
for(int i=1;i;i=i*2)
{
p=0;
for(int j=n-i+1;j<=n;j++)y[++p]=j;
for(int j=1;j<=n;j++)
if(sa[j]>i)y[++p]=sa[j]-i;
for(int j=1;j<=m;j++)c[j]=0;
for(int j=1;j<=n;j++)c[x[y[j]]]++;
for(int j=1;j<=m;j++)c[j]+=c[j-1];
for(int j=n;j;j--)sa[c[x[y[j]]]--]=y[j];
swap(x,y);
p=2;
x[sa[1]]=1;
for(int j=2;j<=n;j++)
if(y[sa[j]]==y[sa[j-1]]&&y[sa[j]+i]==y[sa[j-1]+i])x[sa[j]]=p-1;
else x[sa[j]]=p++;
if(p>n)return;
m=p;
}
}
void 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;
}
}
int main()
{
n=read();
scanf("%s",s+1);
for(int i=1;i<=n;i++)a[i]=s[i];
SA(n,233);
Height();
for(int i=2;i<=n;i++)
{
for(int j=height[i-1]+1;j<=height[i];j++)
{
int k=i;
while(height[k]>=j)k++;
printf("%d\n",k-i+1);
}
}
return 0;
} 
京公网安备 11010502036488号