SA 后缀数组

2018/01/23 12:55
阅读数 31

#SA 后缀数组 首先一定要确定$SA$是个什么东西 $SA[i]$表示的是排名为$i$的后缀是哪一个 至于后缀$i$的排名是多少,那个是$rank[i]$


当然啦 最最最难懂的就是基数排序 要是不用基数排序,每次对于一个二元组直接$sort$一下 这样的复杂度是$O(nlog^2)$

对于二元组的基数排序应该是这样做的: 首先把所有元素按照最后一维丢到依次对应的桶里面 然后顺次取出 再按照第一维依次丢入 再顺次取出 这样就可以排序啦


先把代码丢出来

bool cmp(int i,int j,int k){return y[i]==y[j]&&y[i+k]==y[j+k];}
void GetSA()
{
	int m=30;
	for(int i=1;i<=n;++i)t[x[i]=a[i]]++;
	for(int i=1;i<=m;++i)t[i]+=t[i-1];
	for(int i=n;i>=1;--i)SA[t[x[i]]--]=i;
	for(int k=1;k<=n;k<<=1)
	{
		int p=0;
		for(int i=0;i<=m;++i)y[i]=0;
		for(int i=n-k+1;i<=n;++i)y[++p]=i;
		for(int i=1;i<=n;++i)if(SA[i]>k)y[++p]=SA[i]-k;
		for(int i=0;i<=m;++i)t[i]=0;
		for(int i=1;i<=n;++i)t[x[y[i]]]++;
		for(int i=1;i<=m;++i)t[i]+=t[i-1];
		for(int i=n;i>=1;--i)SA[t[x[y[i]]]--]=y[i];
		swap(x,y);
		x[SA[1]]=p=1;
		for(int i=2;i<=n;++i)x[SA[i]]=cmp(SA[i],SA[i-1],k)?p:++p;
		if(p>=n)break;
		m=p;
	}
}

首先,第一次做$k=0$时 相当于每个后缀的第二维都是一样的 所以,直接按照第一维(也就是自己的值) 进行一次基数排序

接下来 每次基数排序都要利用到上一次的值

还记得吧,基数排序是先按照第二维从小往大拍 那么,我们就先把第二维的顺序搞出来 首先最小的一定就是没有第二维的东西 所以我们先把这些数直接丢进数组里面 接下来就是有第二维的东西啦 第$i$位的第二维是啥?$rank[i+k]$ 所以,从小到达枚举$SA$,这样保证第二维从小往大 那么,只要$SA[i]>k$ 就证明它是一个东西的第二维 所以,把$SA[i]-k$丢到数组里面去就好啦

这样的话,按照第二维就拍好啦 再来依次按照第一维丢到桶里面去 做一遍基数排序就好啦 这样就能够求出$SA$啦

看起来很简单诶。。 只是数组不要搞混了 一定搞清楚每个数组是干啥的 比如我的代码 $SA$是后缀数组,$SA[i]$表示排名为$i$的串是哪一个 $rank$相当于排名,$rank[i]$表示第$i$个串的排名 $x,y$两个数组是记录顺序的 分别记录第一维和第二维的排序的顺序 $t$是桶

这样我们就很愉快的求出了$SA$ 还有一个数组$Height$ $Height[i]$表示串$SA[i]$与$SA[i-1]$的最长公共前缀的长度 比如说,现在要求后缀$i$与$j$的最长公共前缀 那就只需要求$min(Height[i]),i \in [rank[i]+1,rank[j]]$ 因为已经按照字典序排好序啦

$Height$显然可以暴力求 但是太不优美 我们有$Height[rank[i]]>=Height[rank[i-1]]-1$ 证明(来自$hihoCoder$)

设$suffix(k)$是排在$suffix(i-1)$前一名的后缀, 则它们的最长公共前缀是$height[rank[i-1]]$ 那么$suffix(k+1)$将排在$suffix(i)$的前面(这里要求$height[rank[i-1]]>1$,如果$height[rank[i-1]]≤1$,原式显然成立) 并且$suffix(k+1)$和$suffix(i)$的最长公共前缀是$height[rank[i-1]]-1$, 所以$suffix(i)$和在它前一名的后缀的最长公共前缀至少是$height[rank[i-1]]-1$

那么,我们按照$rank$的顺序来求$Height$就行啦

	for(int i=1;i<=n;++i)Rank[SA[i]]=i;
	for(int i=1,j=0;i<=n;++i)
	{
		if(j)j--;
		while(a[i+j]==a[SA[Rank[i]-1]+j])++j;
		height[Rank[i]]=j;
	}

我现在也不是很熟 以后多做点题我再接着补

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部