Copyright By

注意事项

讲评人没有实力，也没有烤鸭皮皮，所以对于接下来提到的一些结论将不予证明，感兴趣的可以自己bdfs一下，或者课后询问讲评人

部分定义不准确，并不形式化，是讲评人自己思考后的结果

如果觉得自己的想法与讲评人有不同或者算法更优，可提出自己的见解

---

定义

后缀 形如$s[i...n]$的子串，记做$suffix(i)$

字典序 不想讲~，跟字典一样

注意空串字典序小于任何非空串

新的定义

后缀数组sa 将s的n个后缀排完序放入数组，$sa[i]$ 就表示排名为i的后缀是（这里用开始字符的位置表示）

名次数组rk $rk[i]$表示$suffix[i]$的排名

hei数组 排名为i的后缀与排名为i-1的后缀的最长公共前缀

计数排序

不多说，直接上代码：

时间复杂度$O(n+m)$

int x[AwA], res[AwA];
int cnt[AwA];

inline void CountSort() {
    memset(cnt, 0, sizeof cnt);
    int m = 0;
    //x[i]在0~m范围内
    for (int i = 1; i <= n; i++) m = max(m, x[i]);
    for (int i = 1; i <= n; i++) cnt[x[i]]++;
    for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for (int i = n; i; i--) res[cnt[x[i]]--] = i;
}

倍增求sa

简单来说就是把后缀变为长度大于等于n的字符串，由于后面部分为空串，所以不影响字典序

比较两个串变为分别比较两个串的前半部分和后半部分

那么两次计数排序可得

空间复杂度$O(n)$

时间复杂度$O(nlogn)$

注意：代码中有几个数组需要开2倍大小（建议全开2倍）

int n;
int x[AwA << 1], y[AwA << 1], cnt[AwA];
//x临时rk数组,y临时数组,cnt桶
int sa[AwA << 1];
char s[AwA];

inline void GetSa() {
    for (int i = 1; i <= n; i++) x[i] = s[i] - 'a';
    int m = 0;
    for (int i = 1; i <= n; i++) m = max(m, x[i]);

    memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= n; i++) cnt[x[i]]++;
    for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for (int i = n; i; i--) sa[cnt[x[i]]--] = i;

    for (int k = 1; k <= n; k <<= 1) {
        memset(cnt, 0, sizeof cnt);
        memcpy(y, sa, sizeof y);
        for (int i = 1; i <= n; i++) cnt[x[y[i] + k]]++;
        for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
        for (int i = n; i; i--) sa[cnt[x[y[i] + k]]--] = y[i];

        memset(cnt, 0, sizeof cnt);
        memcpy(y, sa, sizeof y);
        for (int i = 1; i <= n; i++) cnt[x[y[i]]]++;
        for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
        for (int i = n; i; i--) sa[cnt[x[y[i]]]--] = y[i];

        m = 0;
        memcpy(y, x, sizeof y);
        for (int i = 1; i <= n; i++)
            if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k])
                x[sa[i]] = m;
            else x[sa[i]] = ++m;
        if (m == n) break;
    }
}

24.1.12更新：经@优化过常数并附上注释的新代码

#include<bits/stdc++.h>
#define N 10000005
using namespace std;
int n;
int sa[N<<1],x[N<<1],y[N<<1],cnt[N];
string s;
void GetSa()
{
	int m=128;//基数排序的值域
	memset(cnt, 0, sizeof cnt);//对原串字符基数排序，获取各字符排名
	for (int i = 1; i <= n; i++) cnt[x[i]=s[i-1]]++;
	for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
	for (int i = n; i; i--) sa[cnt[x[i]]--] = i;
	for(int k=1;k<=n;k<<=1)//倍增求SA，k为当前处理串长
	{
		int p=0;//根据上一轮求得的sa数组计算下一轮根据第二关键字排序的顺序
		for(int i=n;i>n-k;i--) y[++p]=i;//第二关键字排序其实就是把超出串范围（即 sa[i]+w>n）的 sa[i] 放到 sa 数组头部
		for(int i=1;i<=n;i++) if(sa[i]>k) y[++p]=sa[i]-k;//然后把剩下的依原顺序放入
		memset(cnt,0,sizeof cnt);//对第一关键字进行基数排序
		for(int i=1;i<=n;i++) cnt[x[y[i]]]++;
		for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
		for(int i=n;i;i--) sa[cnt[x[y[i]]]--]=y[i];
		swap(x,y);m=0;//将 y 赋为 x 并重新计算 x（临时排名）
		for(int i=1;i<=n;i++)
			if(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) x[sa[i]]=m;
			else x[sa[i]]=++m;
		if(m==n) break;//如果已经得出m个排名即为排序完毕直接结束
	}
}
int main()
{
	cin>>s;
	n=s.size();
	GetSa();
	for(int i=1;i<=n;i++) cout<<sa[i]<<' ';
	return 0;
}

求hei数组

定义$h[i]=hei[rk[i]]$，即i后缀与前一名后缀的最长公共前缀长度

满足$h[i-1]-1\leq h[i]$

由该性质可得代码：

空间复杂度$O(n)$

时间复杂度$O(n)$

int sa[AwA<<1],rk[AwA],hei[AwA];

inline void GetHei() {
    for (int i = 1; i <= n; i++) rk[sa[i]] = i;
    //利用sa求rk

    int h = 0;
    //维护h数组的上一个值
    for (int i = 1; i <= n; i++) {
        if (rk[i] == 1) {
            //第一名显然hei[1]=0
            hei[1] = 0;
            continue;
        }
        if (h) h--;
        //h[i]>=h[i-1]-1
        int j = sa[rk[i] - 1];
        //尝试扩展
        while (i + h <= n && j + h <= n && s[i + h] == s[j + h]) h++;
        hei[rk[i]] = h;
    }
}

24.1.12更新： 由@提供的精简抽象代码

void gethei()
{
	for(int i=1;i<=n;i++) rk[sa[i]]=i;//根据sa求rk数组
	for(int i=1,h=0;i<=n;hei[rk[i++]]=h)//h为前缀长度，遍历每个后缀，循环结束后h即为height
 		for(h?h--:0;s[i+h]==s[sa[rk[i]-1]+h];h++);//hei最小为上一个hei-1,然后扩展
}

---

至此，sa，rk，hei三个数组就求完了

一个简单的应用

给定字符串s，和m个询问，每个询问给出两个值x,y

求以$s[x]$为起点和以$s[y]$为起点的最长公共子串长度

最长公共子串长度转换为hei数组的区间最小

可用st表维护

时间复杂度$O(nlogn+mlogn)$