后缀排序学习笔记

pengchujie / 2023-08-26 / 原文

传送门

定义\(sa_i\)表示排名为 \(i\) 的后缀编号是什么。

例：\(ababa\)

\(sa_1=5,sa_2=3,sa_3=1,sa_4=4,sa_5=2\)

思路理解：

先根据第一位排序，确定最初的\(sa\)

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

先用桶排，确定每个字符有多少个(第一行数组\(c\))，再用前缀和(第二行数组\(c\))，确定字典序小于等于这个字符的字符个数，最后再用\(c\)确定数组\(sa\)(注：第一位相同时，位置越后，排名越后)

然后考虑倍增（为什么倍增可以我也不知道）

for(ll k=1;k<=n;k<<=1)

然后用基数排序的思想，在第一关键字的基础上，用第二关键字排序

定义\(y_i\)为排名为第 \(i\) 的第二关键字

然后根据上次排序的\(sa\)来确定\(y\)

ll num=0;
for(ll i=n-k+1;i<=n;i++) y[++num]=i;
for(ll i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k;

首先，因为后\(k\)位是没有第二关键字的，所以按照字典序他们的第二关键字最小，所以直接存在于\(y\)中。

否则若排名为\(i\)的后缀可作为其他位置的第二关键字，即\(sa_i>k\)，就把他放在对应的第一关键字(\(x_{sa_i-k}\))中

然后从后往前更新\(sa\)

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

swap(x,y);
num=1;x[sa[1]]=1;
for(int i=2;i<=n;i++)
{	
if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])x[sa[i]]=num;
else x[sa[i]]=++num;
}

这里一起讲：

除第一次外(因为第一次是在循环外更新\(x_i\)，即按照第一关键字排序)，其他都是在循环内更新\(x_i\)

我们在上一次循环中已经更新了第一关键字了，所以只需要根据第二关键字更新排名即可，即

for(int i=n;i>=1;i--){sa[c[x[y[i]]]--]=y[i];y[i]=0;}

然后，因为在本次循环中，已经更新完了\(y_i\)，所以在下一次循环中，\(x_i\)和\(y_i\)将一同作为第一关键字出现 ，那么下一个循环中的第一关键字相同的条件为\(x_i=x_j\)并且\(y_i=y_j\)

最后说一下为什么从后往前：因为前面的\(1\)~\(k\)的数已经是没有第二关键字了，按照字典序他们应该在第一关键字相同的所有后缀中的最前面，所以让他们最后被处理，即从后往前排序

例如：

上代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1114514;
char s[N];
ll c[N],x[N],sa[N],y[N];
ll n,m;
void get_SA()
{
	for(ll i=1;i<=n;i++) ++c[x[i]=s[i]];
	for(ll i=2;i<=m;i++) c[i]+=c[i-1];
	for(ll i=n;i>=1;i--) sa[c[x[i]]--]=i;
	for(ll k=1;k<=n;k<<=1)
	{
		ll num=0;
		for(ll i=n-k+1;i<=n;i++) y[++num]=i;
		for(ll i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k;
		for(ll i=1;i<=m;i++) c[i]=0;
		for(ll i=1;i<=n;i++) ++c[x[i]];
		for(ll i=2;i<=m;i++) c[i]+=c[i-1];
		for(ll i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i];
		swap(x,y);
		x[sa[1]]=1;
		num=1;
		for(ll i=2;i<=n;i++)
		{
			if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]) x[sa[i]]=num;
			else x[sa[i]]=++num;
		}
		if(num==n) break;
		m=num;
	}
	for(ll i=1;i<=n;i++)
	printf("%lld ",sa[i]);
	puts("");
}
int main()
{
	cin>>s+1;
	n=strlen(s+1),m=122;
	get_SA();
	return 0;
}