后缀数组


定义:

先定义一个字符串s,假设它的长度为n,s[i]表示第i个元素 ,s[i…]代表以s[i]开头且包含s[i]的后缀。我们定义新的数组 sa[i]为一个0-n的排列,且sa[i]为后缀s[i…]在所有后缀中按 照从小到大排序的排名。最后定义rank是sa的反函数。

sa数组也称为后缀数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//定义以s[i]开头的后缀是suf(i)
//后缀数组性质:suf(sa[i])<suf(sa[i+1])
//模版从下标为1的地方开始,引入的字符串下标也要从下标为1开始

struct SA{
static const int MAXN=2e5+555;
static int lg[MAXN];
int h[MAXN][20],rank[MAXN],sa[MAXN],n;

void init(char*s,int len){//第一个参数要是从下标为1开始的字符串,第二个参数是要从下标为
static int x[MAXN],y[MAXN],c[MAXN];//全部是辅助数组
n=len;//初始化后缀数组内部的n->s后缀数组长度
int m=1000;//桶的大小
for(int i=1;i<=n;i++)sa[i]=y[i]=0;//初始化sa,y
for(int i=1;i<=n;i++)x[i]=s[i];//把s复制到x
for(int i=1;i<=m;i++)c[i]=0;//初始化c
for(int i=1;i<=n;i++)c[x[i]]++;//对x计数
for(int i=1;i<=m;i++)c[i]+=c[i-1];//计数前缀和
for(int i=n;i>=1;i--)sa[c[x[i]]--]=i;//按照计数排序后的结果
for(int k=1;k<=n;k<<=1){
int num=0;
for(int i=n-k+1;i<=n;i++)y[++num]=i;
for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
for(int i=1;i<=m;i++)c[i]=0;//初始化c
for(int i=1;i<=n;i++)c[x[i]]++;//对x计数
for(int i=1;i<=m;i++)c[i]+=c[i-1];//计数前缀和
for(int i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i];
for(int i=1;i<=n;i++)y[i]=x[i];
for(int i=1;i<=n;i++)x[i]=0;
num=1;
x[sa[1]]=1;
for(int i=2;i<=n;i++){
if((y[sa[i]]!=y[sa[i-1]])||(y[sa[i]+k]!=y[sa[i-1]+k])){
x[sa[i]]=++num;
}
else x[sa[i]]=num;
}
if(num>=n)break;
m=num;
}
for(int i=1;i<=n;i++)rank[i]=x[i];
//获取高度数组
int k=0;
for(int i=1;i<=n;i++){
if(k)k--;
int j=sa[rank[i]-1];
while((i+k<=n)&&(j+k<=n)&&(s[i+k]==s[j+k]))k++;
h[rank[i]][0]=k;
}
//对高度数组做rmq
for(int j=1;j<20;j++){
int d=1<<j;
for(int i=1;i+2*d-1<=n;i++)h[i][j]=min(h[i][j-1],h[i+d][j-1]);
}
if(lg[1]!=0)for(int i=1;i<MAXN;i++)lg[i]=trunc(log(i+0.5)/log(2));
}

int lcp(int x,int y){//注意没有下标检查,如果访问越界的话,会错。
int L=min(rank[x],rank[y])+1;
int R=max(rank[x],rank[y]);
int k=lg[R-L+1];
return min(h[L][k],h[R-(1<<k)+1][k]);
}
}sa;
int SA::lg[SA::MAXN];

文章作者: fightinggg
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 fightinggg !
  目录