后缀数组炒鸡简单的
〇、朴素解法
(O(N^2 log N))
一、字符串哈希
(O(N))的时间求出
(O(1))比较字符串是否相等
(O(N log^2 N))
使用 Hash 来构造后缀数组的好处在于时间复杂度较低，并且珂以动态维护（珂以使用set），坏处在于 Hash 的不稳定性。
二、倍增法
(2^k) 的子串的排名
(O(N logN))
完整代码
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
inline void write(register int x)
{
if(!x)putchar('0');if(x<0)x=-x,putchar('-');
static int sta[20];register int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
char s[N];
int n,m;
int rak[N],tp[N],sa[N],tax[N];
inline void Qsort()
{
for(register int i=1;i<=m;++i)
tax[i]=0;
for(register int i=1;i<=n;++i)
++tax[rak[i]];
for(register int i=1;i<=m;++i)
tax[i]+=tax[i-1];
for(register int i=n;i>=1;--i)
sa[tax[rak[tp[i]]]--]=tp[i];
}
inline void suffixsort()
{
m=80;
for(register int i=1;i<=n;++i)
rak[i]=s[i]-'0',tp[i]=i;
Qsort();
for(register int w=1,p=0;p<n;m=p,w<<=1)
{
p=0;
for(register int i=1;i<=w;++i)
tp[++p]=n-w+i;
for(register int i=1;i<=n;++i)
if(sa[i]>w)
tp[++p]=sa[i]-w;
Qsort();
swap(tp,rak);
rak[sa[1]]=p=1;
for(register int i=2;i<=n;++i)
rak[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w])?p:++p;
}
for(register int i=1;i<=n;++i)
write(sa[i]),putchar(' ');
}
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
suffixsort();
return 0;
}
但是这仍然在较大数据范围时比较吃力（毒瘤）
三、DC3
常数巨大
①先将后缀分成两部分，然后对第一部分的后缀排序;
②利用①的结果，对第二部分的后缀排序;
③将①和②的结果合并，即完成对所有后缀排序;
(O(N))，但常数极大，在较小数据范围时与倍增算法相比无明显优势，且实现复杂，性价比较低
比倍增法跑的还慢的dc3
#include<bits/stdc++.h>
#define N 1000005
using namespace std;
inline void write(register int x)
{
if(!x)putchar('0');if(x<0)x=-x,putchar('-');
static int sta[20];register int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
char s[N];
int str[N*3],sa[N*3],rank[N],height[N];
int id[N];
inline bool equal(register int *str,register int a,register int b)
{
return str[a]==str[b]&&str[a+1]==str[b+1]&&str[a+2]==str[b+2];
}
inline bool cmp3(register int *str,register int *nstr,register int a,register int b)
{
if(str[a]!=str[b])
return str[a]<str[b];
if(str[a+1]!=str[b+1])
return str[a+1]<str[b+1];
return nstr[a+b%3]<nstr[b+b%3];
}
inline void Qsort(register int *str,register int *sa,register int *res,register int n,register int m)
{
for(register int i=0;i<m;++i)
id[i]=0;
for(register int i=0;i<n;++i)
++id[str[sa[i]]];
for(register int i=0;i<m;++i)
id[i+1]+=id[i];
for(register int i=n-1;i>=0;--i)
res[--id[str[sa[i]]]]=sa[i];
}
inline void dc3(register int *str,register int *sa,register int n,register int m)
{
#define F(x) ((x)/3+((x)%3==1?0:one))
#define G(x) ((x)<one?(x)*3+1:((x)-one)*3+2)
int *nstr=str+n,*nsa=sa+n,*tmpa=rank,*tmpb=height;
int len=0,num=0,zero=0,one=(n+1)/3;
for(register int i=0;i<n;++i)
if(i%3)
tmpa[len++]=i;
str[n]=str[n+1]=0;
Qsort(str+2,tmpa,tmpb,len,m);
Qsort(str+1,tmpb,tmpa,len,m);
Qsort(str+0,tmpa,tmpb,len,m);
nstr[F(tmpb[0])]=num++;
for(register int i=1;i<=len-1;++i)
nstr[F(tmpb[i])]=equal(str,tmpb[i-1],tmpb[i])?num-1:num++;
if(num<len)
dc3(nstr,nsa,len,num);
else
for(register int i=0;i<len;++i)
nsa[nstr[i]]=i;
if(n%3==1)
tmpa[zero++]=n-1;
for(register int i=0;i<len;++i)
if(nsa[i]<one)
tmpa[zero++]=nsa[i]*3;
Qsort(str,tmpa,tmpb,zero,m);
for(register int i=0;i<len;++i)
tmpa[nsa[i]=G(nsa[i])]=i;
for(register int i=0,j=0,k=0;k<n;++k)
if(j>=len||(i<zero&&cmp3(str,tmpa,tmpb[i],nsa[j])))
sa[k]=tmpb[i++];
else
sa[k]=nsa[j++];
}
int main()
{
scanf("%s",s);
int n=strlen(s);
str[n]=0;
for(register int i=0;i<n;++i)
str[i]=s[i];
dc3(str,sa,n+1,256);
for(register int i=1;i<=n;++i)
write(sa[i]+1),putchar(' ');
return 0;
}
四、SA-IS
待填坑
五、后缀数组的一些应用
所有操作都基于Height数组
Height[i]=lcp(sa[i],sa[i-1])，即排名为i的后缀与排名为i−1的后缀的最长公共前缀
求法：
inline void GetHeight()
{
int k=0;
for(register int i=1;i<=n;++i)
{
if(k)
--k;
int j=sa[rak[i]-1];
while(s[i+k]==s[j+k])
++k;
Height[rak[i]]=k;
}
}
rak:从第i个位置开始的后缀的排名
rak珂以根据rak[sa[i]]=i，sa[rak[i]]=i快速求出
有了Height数组后就珂以胡作非为
1.两个后缀的最大公共前缀
lcp(x,y)=min(Height[x~y])，用rmq维护，O(1)查询
2.可重叠最长重复子串
Height数组里的最大值
3.不可重叠最长重复子串
首先二分答案x，对Height数组进行分组，保证每一组的min_Height都>=x
依次枚举每一组，记录下最大和最小长度，当sa[maxlen]−sa[minlen]>=x那么可以更新答案
4.本质不同的子串的数量
枚举每一个后缀，第i个后缀对答案的贡献为len−sa[i]+1−Height[i]
