• 周五. 10月 7th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

后缀数组SA模板详解

admin

11月 28, 2021

也许应该叫后缀排序,是求出(sa[i])(rk[i])的一种算法。
(sa[i])代表排名为i的后缀的开始位置。
(rk[i])代表开始位置为(i)的后缀的排名。
这是实现比原理要复杂的算法。
先求出(sa[i])之后再求出(rk[i])
考虑先求出长度为1时候的(sa[i])数组。这个时候(sa[i])代表长度为1排名为i的子串的开始位置。然后倍增求长度数为2时候的(sa[i])数组。直到长度大于(n)(也就是字符串的长度)(超出长度的地方就是空字符)。然后考虑如何用长度为x时的(sa[i])数组求长度为(2x)时的(sa[i])数组。把长度为(2x)的串从中间劈开得到(a),(b)两个串,(a,)(b)的排名已经知道其实就是做一遍以(a)排名,(b)排名为第一第二关键字的排序。
知道(sa[i])之后求(rk[i])易如反掌,它们就是权值和下标相反的两个数组。
下面是求sa数组的代码。

void get_sa(){
	for(int i=1;i<=n;i++)c[x[i]=s[i]]++;
	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;i>=n-k+1;i--)y[++num]=i;//y[]第二关键字排名为num的第一关键字位置。 
		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;
		for(int i=1;i<=n;i++)c[x[i]]++;
		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],y[i]=0;//第一第二关键字的基数排序 
		swap(x,y);
		num=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])?num:++num;
		if(n==num)break;
		m=num;
	}
	for(int i=1;i<=n;i++)printf("%d ",sa[i]);
}

把代码拆开看

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

这里是基数排序,但不完全是基数排序。
它的作用是求出上面提到的长度为1时的(sa)数组。
(s)是原串数组,(c)是基数排序时用的桶,(x[i])(i)位置上的字符,(m)是编号的值域也就是桶的大小。
了解这个基数排序对了解后缀数组的实现十分重要。
第一个(for)是把出现的字符计数。第二个(for)是求前缀和。
考虑这个前缀和数组的意义是什么?
(c[i])就是排名小于等于字符i的个数。换种说法(c[i])是字符i的最大的排名。
假设桶长这样

求完前缀和之后长这样

从小到大
第一个出现的字母排第一,第二个出现的字母有三个,所以最大排名是4。。。
最后一个for就是把这些字符的排名求出。
至于为什么写,为什么要倒着循环,其实在求长度为1的串时并不重要。但之后以两个关键字排序时很重要

		int num=0;
		for(int i=n;i>=n-k+1;i--)y[++num]=i;//y[num]第二关键字排名为num的第一关键字位置。 
		for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;

y数组的意义在注释中。

比如要求长度为4的串,以最后一个点为开始的串后半部分完全是空的,排序一定是最靠前的,第一个循环主要处理这种情况。这里第一个循环正着反着循环都没问题。
第二个循环处理剩下部分

	for(int i=1;i<=m;i++)c[i]=0;
	for(int i=1;i<=n;i++)c[x[i]]++;
	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],y[i]=0;

这个部分是基数排序。跟第一部分十分相似。
不过(x)数组代表以i开始的串的编号。
这里重点看最后一个循环,(c[i])相当是求出了编号为(i)的串根据第一关键字排序的上界。
之后根据排好序的第二关键字倒着赋排名。
模拟一遍可以更好理解。

	swap(x,y);
	num=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])?num:++num;
	if(n==num)break;
	m=num;

最后的部分就是根据排序结果赋给每个后缀新的编号。
当编号数位(n)时代表已经对所有的(n)个后缀完成了排序,程序就可以结束了。

(height)数组是常用的辅助数组(做做题就知道了)
(height[i])代表排名为i的后缀与排名为(i-1)的后缀的最长公共前缀。
为了不产生混淆,写成(height[rk[i]])
如何求这个辅助数组?
直接求并不好求,但是有这个性质:(height[rk[i]]=>height[rk[i-1]]-1)
(height[rk[i-1]]<=1)时这个式子显然成立。
考虑(height[rk[i-1]]>1)

每个矩形代表一个后缀,在图中按字典序的大小排列放置。
下面的字母代表这个后缀在串中起始位置。
(k+1)(i)代表的串其实是(k)(i-1)代表的串砍去第一个字母。所以(height[rk[i]]=>height[rk[i-1]]-1)

总代码如下

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=2010000;
int c[N],x[N],y[N],sa[N],rk[N],height[N],n,m;
char s[N];
void get_sa(){
	for(int i=1;i<=n;i++)c[x[i]=s[i]]++;
	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;i>=n-k+1;i--)y[++num]=i;//y[]第二关键字排名为num的第一关键字位置。 
		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;
		for(int i=1;i<=n;i++)c[x[i]]++;
		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],y[i]=0;//第一第二关键字的基数排序 
		swap(x,y);
		num=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])?num:++num;
		if(n==num)break;
		m=num;
	}
	for(int i=1;i<=n;i++)printf("%d ",sa[i]);
}
void get_height(){
	for(int i=1;i<=n;i++)rk[sa[i]]=i;
	int k=0; 
	for(int i=1;i<=n;i++){//i是原串的下标 
		if(rk[i]==1)continue;
		if(k)k--;//height[rk[i]]>=height[rk[i-1]]-1 
		int j=sa[rk[i]-1];
		while(s[i+k]==s[j+k]&&i+k<=n&&j+k<=n)k++;
		height[rk[i]]=k;//height的下标是排名 
	}
	for(int i=1;i<=n;i++)printf("%d ",height[i]);
}
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	m=122;
	get_sa();
	get_height();
	return 0;
}

发表回复

您的电子邮箱地址不会被公开。