差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:hotpot:后缀数组 [2020/09/03 16:36]
lotk 创建
+++ 2020-2021:teams:hotpot:后缀数组 [2020/09/03 19:55] (当前版本)
lotk
@@ 行 1: / 行 1: @@
 ======后缀数组======
+=====基本定义与概念=====
+后缀：$suf(i)$ 代表字符串 $s$ 从 $i$ 位置开始的后缀（由 $s[i] ~ s[n-1]$ 组成的字符串）
+$sa[i]$ ：是一个一维数组，保存了对字符串 $s$ 所有后缀排序后的结果。$sa[i]$ 代表第 $i$ 小的串在原串中的位置。
+$rnk[i]$ ：是一个一维数组，按起始位置保留了每个后缀的排名。$rnk[i]$则为$suf(i)$在所有后缀中的排名。$(ps: rnk[sa[i]] = i)$
+高度数组：$hgt[i]$ 是一个数组，保存了相邻两个后缀的最长公共前缀 $(LCP)$ 的长度。
+=====构造和优化=====
+朴素的构造这样一个数组，最显然的方式显然是直接快速排序。时间复杂度 $O(n^2logn)$，显然很难满足我们大部分使用的需要。
+因此，我们采取倍增的思想来对这些后缀排序。
+假设我们对 $hehehda$ 这样的一个字符串的后缀进行排序。
+从每个位置开始，长度为$2^0$的字串的排序为：
+{{:2020-2021:teams:hotpot:后缀1.png?600|}}
+为了求出长为 $2^1$ 的字符串的排名，我们以每个位置 $i$ 开始,长度为 $2^0$ 的排名为第一关键字，$i+2^0$ 位置的排名为第二关键字来进行排序，$i+2^0 ≥ n$ 的部分我们就值为 $-1$
+{{:2020-2021:teams:hotpot:后缀2.png?600|}}
+重复以上过程，我们可以求出长度为 $2^2$ 的排序结果：
+{{:2020-2021:teams:hotpot:后缀3.png?600|}}
+不难看出，这个时候，我们已经完成了排序，而最坏的情况下，这种算法也可以在 $logn$ 次完成排序。
+用快排进行的话，时间复杂度为 $O(nlognlogn)$
+考虑到所有排序数的范围在 $[-1,n)$ 之间，采取基数排序，能够将复杂度优化到 $nlogn$
+=====模板=====
+下面我们给出一道模板题[[https://www.luogu.com.cn/problem/P3809|P3809 【模板】后缀排序]]
+<code cpp>
+#include<algorithm>
+#include<stack>
+#include<ctime>
+#include<cstring>
+#include<cmath>
+#include<iostream>
+#include<iomanip>
+#include<cstdio>
+#include<queue>
+using namespace std;
+inline int read(){
+	int num=0,f=1;char x=getchar();
+	while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
+	while(x>='0'&&x<='9'){num=num*10+x-'0';x=getchar();}
+	return num*f;
+}
+const int maxn=1000005;
+char s[maxn];
+int n;
+int b[maxn],a[maxn];
+int fir[maxn],sec[maxn],tmp[maxn],buc[maxn];
+int rnk[maxn],sa[maxn];
+void suf_sort(){
+	int tot=n;
+	//对数据离散化，保证数据范围在[0,n]：
+	for(int i=1;i<=n;++i)b[i]=s[i];
+	sort(b+1,b+tot+1);
+	tot=unique(b+1,b+tot+1)-b-1;
+	for(int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+tot+1,s[i])-b;
+	//得到初始排序：
+	for(int i=1;i<=n;++i)++buc[a[i]];
+	for(int i=1;i<=n;++i)buc[i]+=buc[i-1];
+	for(int i=1;i<=n;++i)rnk[i]=buc[a[i]-1]+1;
+	for(int t=1;t<=n;t<<=1){
+		//对第一和第二关键字进行初始化：
+		for(int i=1;i<=n;++i)fir[i]=rnk[i];
+		for(int i=1;i<=n;++i)sec[i]=i+t>n?0:rnk[i+t];
+		//对第二大关键字排序，tmp[i]保存第i大的关键字
+		for(int i=0;i<=n;++i)buc[i]=0;
+		for(int i=1;i<=n;++i)++buc[sec[i]];
+		for(int i=1;i<=n;++i)buc[i]+=buc[i-1];
+		for(int i=1;i<=n;++i)tmp[n - --buc[sec[i]]]=i;//--buc[sec[i]]是一个[0,n)的值，减去它得到[1,n]的值
+		//对第一关键字排序，按照tmp中的顺序领取排名，大的先领取便被放到了后面，完成了排序。
+		for(int i=0;i<=n;++i)buc[i]=0;
+		for(int i=1;i<=n;++i)++buc[fir[i]];
+		for(int i=1;i<=n;++i)buc[i]+=buc[i-1];
+		for(int i=1;i<=n;++i){
+			int t=tmp[i];
+			sa[buc[fir[t]]--]=t;
+		}
+		//根据sa[]数组的顺序求出名次数组rnk[], 注意根据并列情况讨论
+		bool uni=true;
+		for(int i=1,lst=0;i<=n;++i){
+			int t=sa[i];
+			if(!lst)rnk[t]=1;//第一个
+			else if(fir[t]==fir[lst]&&sec[t]==sec[lst])rnk[t]=rnk[lst],uni=false;//和上一个相同
+			else rnk[t]=rnk[lst]+1; //不同
+			lst=t;
+		}
+		if(uni)break;//排序已经完成。
+	}
+	for(int i=1;i<=n;++i)printf("%d ",sa[i]);
+}
+int main(){
+	scanf("%s",s+1);
+	n=strlen(s+1);
+	suf_sort();
+	return 0;
+}
+</code>

CVBB ACM Team

用户工具

站点工具

差别

页面工具