后缀数组 (Suffix Array\text{Suffix Array}) 是一个十分厉害的数据结构，主要维护字符串后缀，并解决一些与 LCP\text{LCP} (最长公共前缀) 的问题。

首先来了解一些基本概念：

子串

在字符串 ss 中，任意取 i≤ji\le j ，那么在 ss 中截取从 ii 到 jj 的这一段即是 ss 的子串。

后缀

后缀即字符串中某个位置 ii 到字符串末尾的子串，定义 ss 的第 ii 个字符为第一个元素的后缀为 suff(i)\text{suff(i)}。

后缀数组

把 ss 的每个后缀按照字典序排序，后缀数组 sa[i] 就表示排名为 ii 的后缀的起始位置下标。

另外一个辅助数组 rank[i] 代表起始位置下标为 ii 的后缀的排名。

两者可以互相映射。

基数排序

一个时间复杂度接近 O(log n)\text{O(log n)} 的排序方法，比快排更优，基础是桶排序。

基数排序思路很简单，就是把数的每一位进行一遍桶排，最后即可得到答案。

例如如下数据：

数据 12 34 56 15 31 52
排名 1 4 6 2 3 5

具体是这样排的：

先按个位进行桶排序：

数据 31 12 52 34 15 56
个位数 1 2 2 4 5 6

再按十位对新得到的序列进行桶排序：

数据 12 15 31 34 52 56
十位数 1 1 3 3 5 5

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn=2e5;
int n,a[maxn],b[maxn],t[11],maxx,p;
int getbit()//得到最大数的位数
{
	for(int i=1;i<=n;i++)
		maxx=max(maxx,a[i]);
	while(maxx)
	{
		maxx/=10;
		p++;
	}
	return p;
}
void radixsort()
{
	p=getbit();
	int radix=1;
	for(int i=1;i<=p;i++)
	{
		for(int j=0;j<=9;j++)
			t[j]=0;//初始化桶
		for(int j=1;j<=n;j++)
		{
			int k=(a[j]/radix)%10;
			t[k]++;//往桶里添加数
		}
		for(int j=1;j<=9;j++)
			t[j]=t[j-1]+t[j];//更新排名，计算比j小的数有多少个
		for(int j=n;j>=1;j--)
		{
			int k=(a[j]/radix)%10;
			b[t[k]]=a[j];//排答案
			t[k]--;
		}
		for(int j=1;j<=n;j++)
			a[j]=b[j];//复制
		radix*=10;//扩大10倍继续排下一位
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	radixsort();
	for(int i=1;i<=n;i++)
		printf("%d ",a[i]);
	return 0;
}

接下来就是重点内容了。

后缀数组主要有两种求法：倍增和 DC3{DC3}，其中倍增比较广泛使用，故以倍增为例进行讲解。

倍增 SA\text{SA} 算法

此处引图和思路来源一个大佬的博客。

流程图如下所示：

例如我们有一个字符串为 banana。

我们首先对单个字符排序(可理解为对每一个后缀的第一个字符排序，与后面进行衔接)，如图：

image.png

对于每个字母我们用字典序给了一个名次，即：

字母 a{a} b{b} n{n}
名次 1 2 3

接下来运用倍增思想，对每个后缀的前两个字符排序，以第一个字符为第一关键字，第二个字符为第二关键字即可，再重新基数排序排名。

然后是 44 个。可知后缀 aa 的前 44 个字符是由后缀 aa 的前 22 个字符和后缀 a+2a+2 的前 22 个字符组成的，以 aa 的前 22 个字符的排名为第一关键字，以 a+2a+2 的前 22 个字符的排名为第二关键字，重新排序：

由于字符串长度小于 88，于是可以结束排序，得到 rank 数组，如下：

i{i} 1 2 3 4 5 6
rank[i]{rank[i]} 4 3 6 2 5 1

同时在排序时可以顺便求出 sa{sa} 数组，如下所示：

i{i} 1 2 3 4 5 6
rank[i]{rank[i]} 6 4 2 1 5 3

知道了思路，怎么代码实现？

像放出全部代码：

void radixsort(int a[],int b[])//基数排序
{
	for(int i=1;i<=m+1;i++)
		t[i]=0;//初始化
	for(int i=1;i<=n;i++)
		t[a[i]]++;//统计
	for(int i=1;i<=m;i++)
		t[i]+=t[i-1];//更新
	for(int i=n;i>=1;i--)
		sa[t[a[b[i]]]--]=b[i];
}
bool check(int r[],int a,int b,int j)
{
	return r[a]==r[b]&&r[a+j]==r[b+j];
}
void get_SA(int a[],int b[])
{
	for(int i=1;i<=n;i++)
	{
		m=max(m,a[i]=s[i]);//赋值，求出最大数
		b[i]=i;//初始顺序
	}
	radixsort(a,b);
	for(int j=1;j<=n;j<<=1)//倍增长度
	{
		int p=0;
		for(int i=1;i<=j;i++)
			b[++p]=n-j+i;
		for(int i=1;i<=n;i++)
			if(sa[i]>j)
				b[++p]=sa[i]-j;
		radixsort(a,b);
		int *t=a;
		a=b;
		b=t;
		a[sa[1]]=p=1;
		for(int i=2;i<=n;i++)
			a[sa[i]]=check(b,sa[i],sa[i-1],j)?p:++p;
		if(p>=n)
			break;
		m=p;
	}
}

我们依次解释：

void radixsort(int a[],int b[])//基数排序
{
	for(int i=1;i<=m+1;i++)
		t[i]=0;//初始化
	for(int i=1;i<=n;i++)
		t[a[i]]++;//统计
	for(int i=1;i<=m;i++)
		t[i]+=t[i-1];//更新
	for(int i=n;i>=1;i--)
		sa[t[a[b[i]]]--]=b[i];
}

这是基数排序的代码。tt 数组是排序的桶，aa 数组是第一关键字，bb 数组是第二关键字， mm 是 aa 数组的范围。

首先先将桶清空，然后将 aa 数组扔进桶中排序，接着更新 tt 数组，此时 tt 数组代表小于等于 ii 的数有多少个，即 ii 的排名 +1{+1}。

最后倒序，将 bb 从大到小(因为 bb 的顺序是按照第二关键字的顺序来排的，第二关键字靠后的，在同一个第一关键字桶中同样靠后)取出，结合第一关键字 aa 数组，−1-1 后得到排名，赋值即可。

for(int i=1;i<=n;i++)
{
	m=max(m,a[i]=s[i]);//赋值，求出最大数
	b[i]=i;//初始顺序
}
radixsort(a,b);

mm 在一开始求出 aa 数组的最大范围，同时一开始只对单个字符排序，所以只用第一关键字即可，即把 aa 赋值，第二关键字 bb 设置为默认即可，第一遍排序。

for(int j=1;j<=n;j<<=1)//倍增长度
{
	int p=0;
	for(int i=1;i<=j;i++)
		b[++p]=n-j+i;
	for(int i=1;i<=n;i++)
		if(sa[i]>j)
			b[++p]=sa[i]-j;
	radixsort(a,b);
	···
}

接着枚举 jj 为倍增长度，开始求第二关键字。

由于从 n−j+1∼nn-j+1\sim n 开始的后缀长度达不到 jj，所以没有第二关键字，排在最前面。

接着遍历一遍，如果 sa[i]>j{sa[} i]>j，那么它可以作为别人的第二关键字。所以把 sa[i]−j{sa[} i]-j 放进第二关键字中。

	···
	radixsort(a,b);
	int *t=a;
	a=b;
	b=t;
	a[sa[1]]=p=1;
	for(int i=2;i<=n;i++)
		a[sa[i]]=check(b,sa[i],sa[i-1],j)?p:++p;
	if(p>=n)
		break;
	m=p;
}

然后进行第二次排序，得到新的 sa{sa} 数组。

接着交换 a,ba,b 数组，因为生成新的第一关键字 aa 数组时要用到旧的，正好此时 bb 数组没用，就把此时的 aa 放进 bb 中。

很明显 a[sa[1]]=1a[sa[1]]=1，赋值即可，然后把 pp 重新设为 11，开始求新的第一关键字。

从 2∼n2\sim n 遍历，此时需要 check 函数，如下所示：

bool check(int r[],int a,int b,int j)
{
	return r[a]==r[b]&&r[a+j]==r[b+j];
}

结合 check 函数，因为 sa[i]{sa[i]} 已经排好序了，所以直接按排名枚举，同时检查 b[sa[i]]{b[sa[i]]} 与 b[sa[i−1]]{b[sa[i-1]]} 是否相同，由于此时 bb 数组保存的是之前的 aa 数组，所以如果排名相同 p++p++，否则不变。

此时得到的 pp 就是不同的字符串的个数，如果 p≥np\ge n，那么周期长度的字符串在原串中不会重复出现，接下来的排序不会改变 rank 值，直接结束即可，否则令 m=pm=p，改变范围。

整个算法时间复杂度为 O(nlogn)\text{O(nlogn)}。

最长公共前缀 LCP\text{LCP}

定义一个新的数组 height[i]{height[i]}。

定义 height[i]=suff(sa[i−1]){height[i]=\text{suff}(sa[i-1])} 和 suff(sa[i])\text{suff}(sa[i]) 的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀，那么有如下性质：

对于任意 rank[j]<rank[k]{rank[j]<rank[k]}，suff(j)\text{suff}(j) 和 suff(k)\text{suff}(k) 的最长公共前缀为：

min⁡(height[rank[j]+1],height[rank[j]+2],⋅⋅⋅,height[rank[k]]) \min(height[rank[j]+1],height[rank[j]+2],···,height[rank[k]])

那么如何快速求出 height{height} 数组呢？

令 h[i]=height[rank[i]]{h[i]=height[rank[i]]}，也就是 suff(i)\text{suff}(i) 和它前一个后缀的最长公共前缀，其中 h{h} 数组满足以下性质：

h[i]≥h[i−1]−1 h[i] \ge h[i-1]-1

证明略过，自己上网查。

具体实现：

void get_high(int sa[])
{
	for(int i=1;i<=n;i++)
		rank[sa[i]]=i;//反推rank
	int j=0;
	for(int i=1;i<=n;i++)
	{
		if(j)
			j--;
		while(i+j<=n&&sa[rank[i]-1]+j<=n&&s[i+j]==s[sa[rank[i]-1]+j])
			j++;
		height[rank[i]]=j;
	}
}

首先通过得到的 sa{sa} 数组反推 rank{rank} 数组，接着看看循环内：

if(j)
	j--;

这个其实是上面性质 h[i]≥h[i−1]−1{h[i]} \ge {h[i-1]-1} 的化用，因为 jj 其实保存的就是 h[i−1]h[i-1]，即 height[rank[i−1]]height[rank[i-1]]。

接着就是粗暴的按照每位依次对比，如果相同长度加 11，然后赋值即可。

综上，基本的后缀数组就讲完了，后缀数组可以完成很多有用的操作，是一个很厉害的数据结构。

Luogu模板 后缀排序(SA)：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn=2e6;
int n,m,k;
char s[maxn];
int sa[maxn],t[maxn];
int a[maxn],b[maxn];
void radixsort(int a[],int b[])//基数排序
{
	for(int i=1;i<=m+1;i++)
		t[i]=0;//初始化
	for(int i=1;i<=n;i++)
		t[a[i]]++;//统计
	for(int i=1;i<=m;i++)
		t[i]+=t[i-1];//更新
	for(int i=n;i>=1;i--)
		sa[t[a[b[i]]]--]=b[i];
}
bool check(int r[],int a,int b,int j)
{
	return r[a]==r[b]&&r[a+j]==r[b+j];
}
void get_SA(int a[],int b[])
{
	for(int i=1;i<=n;i++)
	{
		m=max(m,a[i]=s[i]);//赋值，求出最大数
		b[i]=i;//初始顺序
	}
	radixsort(a,b);
	for(int j=1;j<=n;j<<=1)//倍增长度
	{
		int p=0;
		for(int i=1;i<=j;i++)
			b[++p]=n-j+i;
		for(int i=1;i<=n;i++)
			if(sa[i]>j)
				b[++p]=sa[i]-j;
		radixsort(a,b);
		int *t=a;
		a=b;
		b=t;
		a[sa[1]]=p=1;
		for(int i=2;i<=n;i++)
			a[sa[i]]=check(b,sa[i],sa[i-1],j)?p:++p;
		if(p>=n)
			break;
		m=p;
	}
}
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	get_SA(a,b);
	for(int i=1;i<=n;i++)
		printf("%d ",sa[i]);
	return 0;
}

接着放一些有用的资料和博客，引用了不少：

后缀数组 最详细(maybe)讲解

最详细的后缀数组

[知识点]后缀数组

后缀数组—处理字符串的有力工具(罗穗骞)

感谢以上大佬。

st=>start: 开始
p1=>inputoutput: 把每个字母排序得到第一次的 sa 值
op=>operation: 根据上一次的 sa 值得到第二关键字
p2=>inputoutput: 按现在关键字排序得到新的 sa 值
p3=>inputoutput: 根据现在的 sa 值得到新的第一关键字
p4=>inputoutput: 重新排序
cond=>condition: 排名各不相同？
e=>end: 结束
st->p1->op->p2->p3->cond
cond(yes)->e
cond(no)->p4->op