2020-2021:teams:hotpot:后缀数组

差别

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

到此差别页面的链接

--- 2020-2021:teams:hotpot:后缀数组 [2020/09/03 16:58]
lotk
+++ 2020-2021:teams:hotpot:后缀数组 [2020/09/03 19:55] (当前版本)
lotk
@@ 行 21: / 行 21: @@
 从每个位置开始，长度为$2^0$的字串的排序为：
-{{:2020-2021:teams:hotpot:后缀1.png?200|}}
+{{: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>

2020-2021/teams/hotpot/后缀数组.1599123484.txt.gz · 最后更改: 2020/09/03 16:58 由 lotk