后缀数组(SA)学习笔记()

这玩意真的是给喵人学的吗，谁告诉本喵这个简单让我先学这个的（哭
搞了一天总是在懂和不懂之间反复…难受。

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5; 
char s[N];
int n,m,sum[N],rk[N],sa[N];
int tp[N];
//尝试写注释理一下思路（？ 
void qsort()
{
	for(int i=0;i<=m;i++) sum[i]=0;
	for(int i=1;i<=n;i++) sum[rk[i]]++;
	for(int i=1;i<=m;i++) sum[i]+=sum[i-1];
	for(int i=n;i;i--) sa[sum[rk[tp[i]]]--]=tp[i];
//有没有人浇浇这句话什么意思啊（悲 
//tp[i] 表示第二关键字排名为 i 的串的位置
//rk[tp[i]] 是这个串的第一关键字
//sum[rk[tp[i]]]-- 是这个串按第一关键字排应该塞在哪
//sa[sum[rk[tp[i]]]--] 是 sum[rk[tp[i]]]-- 这个位置放的是哪个串
}
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1),m=200;
	for(int i=1;i<=n;i++) rk[i]=s[i],tp[i]=i;
	qsort();
	for(int w=1,tot=0;tot<n;m=tot,w<<=1)
	{
		//tot现在有几个不同排名
		//w 现在倍增到几 （实际本轮求的区间长度是2*w） 
		tot=0;
		for(int i=n-w+1;i<=n;i++) tp[++tot]=i;
		//这一部分第二关键字是空串 
		for(int i=1;i<=n;i++) if(sa[i]>w) 
			tp[++tot]=sa[i]-w;
		//sa[i] 当前排在第 i 个的串是谁
		//不会了，寄 
		qsort();swap(rk,tp);
		tot=rk[sa[1]]=1;
		for(int i=2;i<=n;i++) 
			rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+w]==tp[sa[i-1]+w])?tot:++tot;
	}
	for(int i=1;i<=n;i++) printf("%d ",sa[i]);
	return 0;
}

完了又绕不明白了/qd

————————

这玩意真的是给喵人学的吗，谁告诉本喵这个简单让我先学这个的（哭
搞了一天总是在懂和不懂之间反复…难受。

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5; 
char s[N];
int n,m,sum[N],rk[N],sa[N];
int tp[N];
//尝试写注释理一下思路（？ 
void qsort()
{
	for(int i=0;i<=m;i++) sum[i]=0;
	for(int i=1;i<=n;i++) sum[rk[i]]++;
	for(int i=1;i<=m;i++) sum[i]+=sum[i-1];
	for(int i=n;i;i--) sa[sum[rk[tp[i]]]--]=tp[i];
//有没有人浇浇这句话什么意思啊（悲 
//tp[i] 表示第二关键字排名为 i 的串的位置
//rk[tp[i]] 是这个串的第一关键字
//sum[rk[tp[i]]]-- 是这个串按第一关键字排应该塞在哪
//sa[sum[rk[tp[i]]]--] 是 sum[rk[tp[i]]]-- 这个位置放的是哪个串
}
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1),m=200;
	for(int i=1;i<=n;i++) rk[i]=s[i],tp[i]=i;
	qsort();
	for(int w=1,tot=0;tot<n;m=tot,w<<=1)
	{
		//tot现在有几个不同排名
		//w 现在倍增到几 （实际本轮求的区间长度是2*w） 
		tot=0;
		for(int i=n-w+1;i<=n;i++) tp[++tot]=i;
		//这一部分第二关键字是空串 
		for(int i=1;i<=n;i++) if(sa[i]>w) 
			tp[++tot]=sa[i]-w;
		//sa[i] 当前排在第 i 个的串是谁
		//不会了，寄 
		qsort();swap(rk,tp);
		tot=rk[sa[1]]=1;
		for(int i=2;i<=n;i++) 
			rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+w]==tp[sa[i-1]+w])?tot:++tot;
	}
	for(int i=1;i<=n;i++) printf("%d ",sa[i]);
	return 0;
}

完了又绕不明白了/qd