SA 学习笔记

后缀数组\(SA\)

后缀数组，维护的是原字符串的每一个后缀，将其按照字典序大小排序，得到一些有用的信息。

首先明确几个数组的定义：

sa[] //sa[i] 表示字典序第 i 小的后缀在原串中的起始位置为 sa[i]\

rk[] //rk[i] 表示原串从 i 位置开始的后缀的字典序的排名\

h[]  //h[i] 表示排名为第 i 的后缀与排名为第 i-1 的后缀的最长公共前缀\

接下来我们考虑每个数组要怎么求解。

求解 \(rk\)

对于 \(rk\) 数组我们考虑倍增法求解，我们从长度为 \(1\) 开始，每次将长度翻倍，得到新的长度中的排名。

具体的，对于每一个位置 \(j\) ，已经求解了长度为 \(i\)，准备求解 长度为 \(2i\) 的。也就是说我们当前已经求解出了 \(s[j-(j+i-1)]\) 和 \(s[(j+i)-(j+2i-1)]\) 这两个字符串的排名，根据字典序的定义，优先比较靠前的串，因此我们将前一个串的排名设为 \(j\) 这个位置的第一关键字，将第二个串的排名设为 \(j\) 这个位置的第二关键字，然后进行双关键字基数排序 ( 可以用 \(sort\) ) 但是复杂度会多一个 \(log\) ，排完序后就可以得到 \(s[j-(j+2i-1)]\) 这个串的排名。不断进行倍增，就可以求出每个后缀的排名了。

特别的，对于 \(j+i > n\) 的，我们直接将 \(0\) 设为 \(j\) 位置的第二关键字即可。

求解 \(sa\)

求完 \(rk\) 之后，根据定义来看，求 \(sa\) 就是一行的事。

sa[rk[i]]=i

求解 \(h\)

\(h\) 数组在 \(sa\) 的题目中相当常见，对于 \(h\) 有两条关键的性质。

• 排名为 \(i\) 的后缀与排名为 \(j\) 的后缀的最长公共前缀 \(=min_{i=l+1}^rh_i\)
• $h(rk_i) \geq h(rk_{i-1})-1 $

第一条性质的正确性是显然的。

我们重点来关注第二条。

我们设 \(k=sa[rk[i-1]-1]\) ，即 \(h(rk_{i-1})=Lcp(k,i-1)\)

• 若 \(h(rk_{i-1}) \leq 1\) ，结论显然成立
• 若 \(h(rk_{i-1}) > 1\) ，此时 \(Lcp(k,i-1) >1\)，我们把两个串的首位丢掉，也就是 \(i\) 和 \(k+1\) 这两个串，因此 \(Lcp(k+1,i)=Lcp(k,i-1)-1\)。由于 \(k\) 排在 \(i-1\) 前面，因此 \(k+1\) 也排在 \(i\) 前面，根据第一条性质，我们可以得到 \(min_{i=rk[k]+1}^{rk[i]}h_i=h(rk_i-1)-1\) ，所以 \(h(rk_i)\geq h(rk_{i-1})-1\)。得证。

根据第二条性质，我们可以按照 \(rk\) 数组的顺序，从小到大依次求解 \(h(rk_1)\)、\(h(rk_2)\)、....... \(h(rk_n)\)，每次答案至少是上一次的答案 \(-1\)，因此就可以在 \(o(n)\) 的复杂度内求解。

int flag=0,rk[N],sa[N],h[N],fi[N],se[N],b[N],g[N],tp[155];

inline void Round(int *a) {
	int mx=0;
	for(int i=1;i<=n;i++) mx=max(mx,a[i]);
	for(int i=0;i<=mx;i++) b[i]=0;
	for(int i=1;i<=n;i++) b[a[i]]++;
	for(int i=1;i<=mx;i++) b[i]+=b[i-1];
	for(int i=n;i>=1;i--) rk[g[i]]=b[a[g[i]]]--;
	for(int i=1;i<=n;i++) g[rk[i]]=i;
}

inline void Qsort() {
	int idx=1;
	for(int i=1;i<=n;i++) rk[i]=g[i]=i;
	Round(se); Round(fi);
	for(int i=2;i<=n;i++)
		rk[g[i]]=(fi[g[i]]==fi[g[i-1]] && se[g[i]]==se[g[i-1]])?rk[g[i-1]]:++idx;
	if(idx==n) flag=1;
}

inline void Getsa() {
	mem(tp); for(int i=1;i<=n;i++) tp[s[i]-'a']=1;
	for(int i=1;i<155;i++) tp[i]+=tp[i-1];
	for(int i=1;i<=n;i++) rk[i]=tp[s[i]-'a'];
	for(int i=1;i<=n && !flag;i<<=1) {
		for(int j=1;j<=n;j++)
			fi[j]=rk[j], se[j]=j+i>n?0:rk[j+i];
		Qsort();
	}
	for(int i=1;i<=n;i++) sa[rk[i]]=i;
}

inline void Geth() {
	int k=0;
	for(int i=1,j;i<=n;i++) {
		if(k) --k;
		j=sa[rk[i]-1];
		while(s[i+k]==s[j+k] && s[i+k]!='|') k++;
		h[rk[i]]=k;
	}
}

板子是根据自己的理解写出来的，比较屑，常数也比较大。

一些经典的套路、例题

P2178 [NOI2015] 品酒大会

对于这一类的题目，可以对于 \(h\) 数组从大到小排序，然后依次将 \(h_i\) 表示的串用并查集连接起来，用并查集维护信息。

[NOI2016] 优秀的拆分

对于这一类，求解与连续重复 \(k\) 次的字符串相关的题目，都可以考虑通过设置关键点的方法，做到在调和级数的复杂度之内求解。

具体的
我们从小到大枚举循环节的长度 \(L\) ，然后依次枚举所有的关键点：\(L\) 、\(2L\) 、....... \(kL\)。

假设当前枚举到了关键点 \(i\) ,我们处理所有的满足左端点在区间 \((i-L,i]\) 之内的，循环次数大于等于 \(2\) 的串的贡献。

我们设 \(A=Lsp(i,i+L)\)，\(B=Lcp(i,i+L)\)。
首先为了限制左端点的位置，我们令 \(A=min(A,L)\)。

于是我们考虑的这些串中最大循环次数为 \(k=\left\lfloor \frac{A+B-1}{L} \right\rfloor +1\)，这样的串共有 \(z=min(A,(A+B-1)\mod L+1)\) 个。

最后再单独考虑循环次数为 \(1\) 的串的贡献(这样可以减少分类讨论的难度)。

这种方法既可以用于求最值，也可以用来求方案数，时间复杂度 \(o(n\ln n)\)。

P4248 [AHOI2013]差异

统计每一个子串作为 \(Lcp\) 的次数，可以在 \(h\) 数组上面跑单调栈。

P4070 [SDOI2016]生成魔咒

动态维护 \(h\) 数组，答案为字符串的本质不同子串个数。\(ans=\frac{n(n+1)}{2}-\sum_{i=1}^nh_i\)。

其余，待更.......