如何读懂后缀数组代码

\author{张若天}
\institute{清华大学}
\date{\today}

附属于/oi

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void mk_sa(int n,int m){
int *x=t,*y=t2;
for(int i=0;i<m;i++) c[i]=0;
for(int i=0;i<n;i++) c[x[i]=s[i]]++;
for(int i=1;i<m;i++) c[i]+=c[i-1];
for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
for(int k=1;k<=n;k<<=1){
int p=0;
for(int i=n-k;i<n;i++) y[p++]=i;
for(int i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
for(int i=0;i<m;i++) c[i]=0;
for(int i=0;i<n;i++) c[x[y[i]]]++;
for(int i=1;i<m;i++) c[i]+=c[i-1];
for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
swap(x,y);
p=1;x[sa[0]]=0;
for(int i=1;i<n;i++){
x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p-1:p++;
}
if(p>=n) break;
m=p;
}
}

第0行解读

1
void mk_sa(int n,int m){

n: 需要排序的字符串长度,字符串使用0到n-1。

m: 初始时字符集大小。

第2-5行解读

1
2
3
4
for(int i=0;i<m;i++) c[i]=0;
for(int i=0;i<n;i++) c[x[i]=s[i]]++;
for(int i=1;i<m;i++) c[i]+=c[i-1];
for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;

x[i]存储了第一关键字(s[i]的值)。
第4个for反着循环为了排序的稳定性。(虽然这次不重要)
sa最后存的是通过1个字符辨别的顺序。

第6行解读

1
for(int k=1;k<=n;k<<=1)

k倍增,代表位置i比较(x[i],x[i+k])组成的二元组。

第8-9行解读

1
2
for(int i=n-k;i<n;i++) y[p++]=i;
for(int i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;

y存储了第二关键字的顺序。
就是第二关键字排第i的为y[i]。
大于等于n-k的排到前面,因为i+k大于等于n。
其他元素第二关键字为x[i+k],他们原来(x[i]时)的顺序是sa[i],所以现在是sa[i]-k。

第10-13行解读

1
2
3
4
for(int i=0;i<m;i++) c[i]=0;
for(int i=0;i<n;i++) c[x[y[i]]]++;
for(int i=1;i<m;i++) c[i]+=c[i-1];
for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];

第一关键字是x[i]。
依然是四个for的基数排序(在第二关键字y基础上对第一关键字x排序),不过和第一次比x[i]变成了x[y[i]]。(第一次相当于y[i]=i)。
比如把a数组3,1,2,5,4排成有序,y可以等于2,3,1,5,4。这样访问a[y[i]]相当于有序了。

第14+行解读

1
2
3
4
5
6
7
8
9
10
11
12
swap(x,y);
p=1;x[sa[0]]=0;
for(int i=1;i<n;i++){
x[sa[i]]=
y[sa[i]]==y[sa[i-1]]
&&
y[sa[i]+k]==y[sa[i-1]+k]
?
p-1:p++;
}
if(p>=n) break;
m=p;

这里x,y互换了。
然后重新计算x数组(下回合的第一关键字)。
x[sa[0]]=0, 位置sa[0]的关键字为0。
y[sa[i]]==y[sa[i-1]]且y[sa[i]+k]==y[sa[i-1]+k],(这里的y是老的x),我们比较的是(老的) (x[i],x[i+k])二元组,这里判断sa[i]是和sa[i-1]相等与否,如果相等,那他们下一次对应的关键字(大小)为p-1(和sa[i-1]相同),否则p++。
若p=n,已经能区分所有后缀了,退出。
下一次的字符集大小(m)是p。

任何形式的使用、转载请注明出处!

评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框