后缀数组

鉴于后缀数组太难复习的原因，特从老博客把本文搬过来。当然有所更新。

后缀数组

后缀数组（Suffix Array）是一个串的所有后缀按照字典序排列形成的指针数组。

约定

1. Index of strings start with$1$.
   字符串以$1$为起点。
2. Let$suf[i]$denotes the suffix of$S$start with$S[i]$. i. e.$S[i,|S|]$.
   $suf[i]$表示以第$i$个元素开头的后缀，即$Suf[i]=S[i,|S|]$。
3. Let$sa[i]$denotes the index of the i-th lexicographically smallest suffix among$suf[1],suf[2],\cdots,suf[|S|]$.
   $sa[i]$表示字典序从小到大排名为$i$的后缀的标号。
4. Let$rk[i]$denotes the lexicographical order of$suf[i]$. i. e. rank of the i-th suffix.
   $rk[i]\Leftrightarrow rank[i]$表达第$i$个后缀的排名。

举一个例子吧。

考虑字符串 banana：

i    : 1 2 3 4 5 6
s[i] : b a n a n a

它的后缀数组为

i   : 1 2 3 4 5 6
sa[i]:6 4 2 1 5 3

表示字典序排第 i 个的后缀的首字母下标。

则每一个后缀对应排序后的位置为：

i    :1 2 3 4 5 6
rk[i]:4 3 6 2 5 1

表示下标为 i 的后缀的排名。

构造

朴素算法：对后缀排序。$O(n)$比较两个字符串的字典序大小。时间复杂度$O(n^2\log_2n)$.

哈希算法：二分 + 哈希在$O(\log_2n)$的时间内比较两个字符串的字典序大小。时间复杂度$O(n\log_2^2n)$.

接下来介绍倍增算法，通过倍增 + 排序的方式在$O(n\log_2n)$的时间内求出后缀数组。

算法过程中，我们通过$O(\log_2n)$轮桶排序来得到每个后缀的排名。在第$j$轮排序中，我们考虑的是所有$\forall i\in[1,|S|],S[i,\min(i+2^j-1,|S|)]$的串的排名，并记录在$rk$中。在这一阶段，$rk$中可能有相同的数值。而当$O(\log_2n)$轮排序结束后，$rk$中的数必然互不相同。

在每一轮排序中，我们会用这一轮的$rk$求出下一轮的$sa$，再由下一轮的$sa$求出它对应的$rk$。然后重复这个过程。一开始，$rk$可以设置为字符对应的 ASCII 的值。

第一部分

假设$rk[i]$表示的是$S[i,\min(i+2^j-1,|S|)]$的排名，那如何得到进行第下一轮的排序？对于$x,y$：

1. 如果$rk[x]<rk[y]$，那么在下一轮排序后，仍然满足$rk[x]<rk[y]$。因为前缀的字典序已经小于，即使延伸一段后缀也不会有影响。大于同理。
2. 如果$rk[x]=rk[y]$，那么我们就比较$rk[x+2^j]$和$rk[y+2^j]$即可。

也就是说，下一轮排序实际上是二元组$(rk[i],rk[i+2^j])$的排序（如果$i+2^j>|S|, 记 rk[i+2^j]=0$）。直观地说 sort 传进去的比较函数就是

bool cmp(int x,int y){
	return rk[x]!=rk[y]?rk[x]<rk[y]:rk[x+(1<<j)]<rk[y+(1<<j)];
}

利用这个将$1,2,\cdots,n$排序后得到的便是下一轮的$sa$。

第二部分

那么如何通过$sa$求出$rk$？我们不能直接$rk[sa[i]]=i$。因为在这其中还会有相等字符串的存在。首先，$rk[sa[1]]=1$。然后对于$i\in[2,|S|]$，我们比较$sa[i-1]$和$sa[i]$的二元组是否相等。如果相等那么排名加 1，否则排名不变。

实现

在实现的时候显然我们不能调用 sort，而必须手写桶排序。而我们也没必要写二元组的桶排序。由于桶排序是稳定排序，因此我们先按照第二关键字排序，再按照第一关键字排序，就能得到下一轮的$sa$。而我们甚至可以直接从这一轮的$sa$得到第二关键字排序后的结果。因此实际上我们只需要按照第一关键字桶排即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;

namespace SA{
	int l;// 字符串长度，1 起点
	int sa[N],rk[N];
	int t[N],bin[N],sz;//sz: 桶的大小
	void qsort(){// 桶排序
        for(int i=0;i<=sz;i++)bin[i]=0;
		for(int i=1;i<=l;i++)bin[rk[i]]++;// 等价于 bin[rk[t[i]]++
		for(int i=1;i<=sz;i++)bin[i]+=bin[i-1];
		for(int i=l;i>=1;i--)sa[bin[rk[t[i]]]--]=t[i];
	}
	void make(char *s){
        l=strlen(s+1),sz=max(l,'z'-'0'+1);// 初始化 l,sz
		for(int i=1;i<=l;i++)t[i]=i,rk[i]=s[i]-'0'+1;// 初始化 t,rk(1 为最高排名）
		qsort();// 对 t 排序，结果转移到 sa 中
		for(int j=1;j<=l;j<<=1){// 开始倍增
			int tot=0;
			for(int i=l-j+1;i<=l;i++)t[++tot]=i;// 这些后缀没有第二关键字，因此排在最前面
			for(int i=1;i<=l;i++)if(sa[i]-j>0)t[++tot]=sa[i]-j;//{sa[i]-j} 按照第二关键字排列
			qsort();
			swap(t,rk);//t 变成上一次的 rk
			rk[sa[1]]=tot=1;
			for(int i=2;i<=l;i++)
				rk[sa[i]]=t[sa[i-1]]==t[sa[i]]&&t[sa[i-1]+j]==t[sa[i]+j]?tot:++tot;
		}
	}
}
char s[N];
int main(){
    scanf("%s",s+1);
	SA::make(s);
	for(int i=1;i<=SA::l;i++)printf("%d",SA::sa[i]);
	return 0;
}

模板题 LuoguP3809

H 数组

利用后缀数组维护信息，需要一些辅助数组。

定义$h[i]$表示$sa[i]$与$sa[i-1]$的 LCP 的长度。

容易发现$\text{LCP}(sa[i],sa[j])=\min_{i<k\le j}h[k]$.

举个例子吧

结论一则：$h[rk[i]]\geq h[rk[i-1]]-1 (1<i\le |S|)$.

证明很显然，直接用 h[i-1] 的⽅案去掉头上的元素。因此我们只需要求$h'[i]=h[rk[i]]$即可求出$h[i]$。

int calc(int x,int y,int len){
    while(x+len<=l&&y+len<=l&&s[x+len]==s[y+len])++len;
	return len;
}
void calc_h_rk(){//h[rk[i]]
    for(int i=1;i<=l;i++)h[i]=(rk[i]==1)?0:calc(i,sa[rk[i]-1],max(h[i-1]-1,0));
}

均摊复杂度$O(n)$.

应用

两个后缀的 LCP

$$\text{LCP}(sa[i],sa[j])=\min_{i<k\le j}h[k]$$

使用 ST 表预处理$h$，可以做到$O(n\log_2n)-O(1)$的时间复杂度。

子串出现次数

$S[L,R]$的出现次数：即 H 数组下标$rk[L]$左右，使得$h$值大于等于$R-L+1$的区间。二分即可。$O(\log_2n)$.

本质不同的子串个数

总数减掉 height 的和。因为两个相同的串$S[L_1,R_1],S[L_2,R_2]$会在$suf[L_1]$和$suf[L_2]$的 H 数组中被算一次。

最小循环表示

对$SS$建后缀数组即可。

最长公共子串

对于$S,T$，求$\text{LCS}(S,T)$：对$S\#T$建 H 数组，然后判一下下标就行了。

字典序第 K 小子串

在 H[rk] 数组上预处理一下差分等等的东西，然后二分即可。

模板

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+5;

struct SA{
    char s[N];
	int l;
	int sa[N],rk[N];
	int t[N],bin[N],sz;
	int h[N],he[N];//h,height
	void qsort(){
        for(int i=0;i<=sz;i++)bin[i]=0;
		for(int i=1;i<=l;i++)bin[rk[t[i]]]++;
		for(int i=1;i<=sz;i++)bin[i]+=bin[i-1];
		for(int i=l;i>=1;i--)sa[bin[rk[t[i]]]--]=t[i];
	}
	void make(){
        l=strlen(s+1),sz=max(l,26);
		for(int i=1;i<=l;i++)t[i]=i,rk[i]=s[i]-'a'+1;
		qsort();
		for(int j=1;j<=l;j<<=1){
			int tot=0;
			for(int i=l-j+1;i<=l;i++)t[++tot]=i;
			for(int i=1;i<=l;i++)if(sa[i]-j>0)t[++tot]=sa[i]-j;
			qsort();
			swap(t,rk);
			rk[sa[1]]=tot=1;
			for(int i=2;i<=l;i++)
				rk[sa[i]]=t[sa[i-1]]==t[sa[i]]&&t[sa[i-1]+j]==t[sa[i]+j]?tot:++tot;
		}
	}
	int move(int x,int y,int len){
        while(x+len<=l&&y+len<=l&&s[x+len]==s[y+len])++len;
		return len;
	}
	void calc_h(){
        for(int i=1;i<=l;i++)
			h[i]=rk[i]==1?0:move(i,sa[rk[i]-1],max(h[i-1]-1,0));
	}
	int st[N][16];//h[sa[i]]~h[sa[i+2^j]] 中的最小值
	void make_st(){
        for(int i=1;i<=l;i++)st[i][0]=h[sa[i]],printf("st[%d,0]:%d\n",i,st[i][0]);
		for(int j=1;(1<<j)<=l;j++){
            int step=1<<(j-1);
			for(int i=1;i+step<=l;i++){
                st[i][j]=min(st[i][j-1],st[i+step][j-1]);
				printf("st[%d,%d]:%d\n",i,j,st[i][j]);
			}
		}
	}
	int lcp(int x,int y){// 返回长度
		if(x==y)return l-x+1;
		x=rk[x],y=rk[y];
		if(x>y)swap(x,y);
		x++;// 取不到 x
		int step=log(y-x+1)/log(2);
		return min(st[x][step],st[y-(1<<step)+1][step]);
	}
};
SA sa;
int main(){
    scanf("%s",sa.s+1);
	sa.make();
	sa.calc_h();
	sa.make_st();
	for(int i=1;i<=sa.l;i++){
        for(int j=1;j<=sa.l;j++){
            if(i!=j&&sa.lcp(i,j))printf("%d %d %d\n",i,j,sa.lcp(i,j));
		}
	}
	return 0;
}
/*
 * BUG#1: bin[i-1] 写成 bin[i+1]
 * 求后缀 (i,j)(rk[i]<rk[j]) 的 LCP，就是求 j in (rk[i],rk[j]] 的 height[j] 的最小值，即 RMQ.
 */