后缀数组（SA）

SA 的用处（经典题型）：

求LCP，LCS，本质不同子串数
出现 xxx 次子串，字符串中不重叠地出现至少两次的最长串长度
最长AA式子串，连续的若干相同子串（AABB式）

首先说一下，本篇博客是本人在oi-wiki学习后缀数组是写下的笔记，更详细的证明等见oi-wiki_SA

后缀数组主要包含两个数组：(sa[ ]) 和 (rk[ ])。

(sa[i])表示所有后缀中字典序第i小的那个后缀。

(rk[i])表示 (i) 后缀的字典序排名。

求后缀数组

模板提交处：P3809 【模板】后缀排序 (SA)

其中倍增求 (SA) 的代码如下（使用基数排序）：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#define N 2000010
template<typename T> inline void read(T &x) {
    x = 0; char c = getchar(); bool flag = false;
    while (isdigit(c)) {if (c == '-') flag = true; c = getchar(); }
    while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }
    if (flag)   x = -x;
}
using namespace std;
char s[N];
int sa[N], rk[N], oldrk[N], id[N], p, n, w, limi;
int bin[N];
int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (register int i = 1; i <= n; ++i)   ++bin[rk[i] = s[i]];
    for (register int i = 1; i <= 300; ++i)   bin[i] += bin[i - 1];
    for (register int i = n; i > 0; --i)    sa[bin[rk[i]]--] = i;
    limi = 300;//注意是limi不是p，因为for一开始时不会执行limi = p
    for (w = 1; w < n; w <<= 1, limi = p) {
    	//处理id 
    	p = 0;						//注意p = 0 
    	for (register int i = n; i > n - w; --i)	id[++p] = i;//注意"i"
    	for (register int i = 1; i <= n; ++i) 
    		if (sa[i] > w)	id[++p] = sa[i] - w;//注意"sa[i] - w"   注意"sa[i]"
    	
    	//处理sa 
    	memset(bin, 0, sizeof(bin));
    	for (register int i = 1; i <= n; ++i)	++bin[rk[id[i]]];
    	for (register int i = 1; i <= limi; ++i)	bin[i] += bin[i - 1];
    	for (register int i = n; i > 0; --i) sa[bin[rk[id[i]]]--] = id[i];
    	
    	//处理rk（去重） 
    	memcpy(oldrk, rk, sizeof(rk));
    	p = 0;						//注意p = 0 
    	for (register int i = 1; i <= n; ++i)//注意"i - 1"  注意"oldrk" 
    		rk[sa[i]] = (oldrk[sa[i]] == oldrk[sa[i - 1]] && oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]) ? p : ++p;
            //注意 + w
       	if (p == n)	break;//小优化:如果已经排好序了，就不用再排了。
    }
    
    for (register int i = 1; i <= n; ++i)   printf("%d ", sa[i]);
    return 0;
}

例题：

字符加密

后缀数组的height数组

(height[i]) 表示 (sa[i]) 后缀和 (sa[i - 1]) 后缀的 (lcp) （最长公共前缀）。

求height数组

我们发现一个规律：

(height[rk[i]] >= height[rk[i - 1]] - 1)

证明感性加玄学（详见oi-wiki_SA）：

假设i - 1的height为5，那么

(O(n)) 代码如下：

for (register int i = 1, k = 0; i <= n; ++i) {
	if (k)	k--;//height[rk[i]] >= height[rk[i - 1]] - 1;
	while(s[i + k] == s[sa[rk[i] - 1] + k])	++k;
	height[rk[i]] = k;
}

至于为什么是 (O(n)) 是因为可以证明 (k--) 的次数是有限的，最多 (n) 次，所以最多加 (2n) 次。

应用

求两子串的最长公共前缀

题意简述：

给定一小写字母组成的字符串，形如 (abababcabcabc)，规定 (s[l][r]) 为(l~r)间的子串，如 (s[2][5] = baba) 。

多次询问，每次给出两组 (l),(r)，求各自 (lcp)。

(len <= 100000, 1 <= l <= r <= len)

分析与解

首先要知道，(lcp(sa[i], sa[j]) = min(height[i...j]))，感性证明一下，就是从 (i) 到 (j) 都没变，那就是他们的 (lcp) 了。

这样，我们已知 (lcp(i, j))， (lcp(l...r, l'..r')) 就用子串长度和 (lcp(i, j)) 取最小者即可。

通过ST表，可以把复杂度降为 (O(nlogn +q))。

比较子串的字典序大小

求完后缀数组后，我们能 (O(1)) 地比较两后缀的大小，现在要比较子串大小，只需把 (lcp(A,B) >= min(|A|, |B|)) 的情况特判掉即可。

有 (sa,rk,height) 数组后过于简单，故不赘述。

求本质不同的子串数

我们按所有后缀以字典序从大到小的顺序考虑。子串数就是后缀的前缀数，这个好求，关键是求出多算的那些相同的子串数。

排序后第 (i) 名串与第 (i - 1) 名串的重叠部分长度为 (lcp(sa[i], sa[i - 1]))，这里多算了 (lcp(sa[i], sa[i - 1])) 个子串，把他们减去即可。

至于只考虑相邻后缀的正确性，据说可以用 (lcp(sa[i], sa[j]) = min(height[i...j])) 来证明。

long long ans = (n * (n + 1)) >> 1;
for (register int i = 2; i <= n; ++i) {
	ans -= height[i];//height[i] = lcp(sa[i], sa[i - 1]);
}

求一个子串的字典序排名

例如，我们求 ABABABD 中 BABA 的字典序排名。

我们可以先求出SA和height数组，然后查询 BABA 所在的后缀 BABABD。然后之前的后缀的前缀字典序一定比它小。因此直接统计一下本质不同的子串数量(len - height)，再加上B,BA,BAB 比它小，就好了。

不过有时候BABABD后缀的 height 可能比4大，这意味着前面所有 BABA... 的串的字典序都比 BABA 大。因此我们直接二分找到最靠下的第一个不包含 BABA 的后缀，这及之前的那些子串一定比 BABA 小，再加上 B,BA,BAB 即可。

求出现至少 (k) 次的最长子串长度

经典例题：牛奶模式

题意简述

给定一字符串，求出现至少 (k) 次的最长子串长度。

(len <= 20000)

分析与解

把子串转换为后缀的前缀，如果有几个相同的子串，那么在排序后的后缀中应该为相邻的一部分，且它们的 (lcp) 一定大于等于子串长度。所以出现至少出现 (k) 次的最长子串长度一定是在排序后连续至少 (k) 个的 (lcp) 的最大值。然后就变成滑动窗口，用单调队列维护即可。

当然，既然求 SA 都到达了 (O(nlogn))，那么二分答案的那个 (log) 也不算什么了。

(Code): my record

字符串中不重叠地出现至少两次的最长串长度

注意到答案具有单调性，故考虑二分。

二分长度 (len)，对于排序后的后缀，找到 (lcp) (>=) (len) 的连续的几段，它们一定出现了至少两次，且长度大于等于 (len)。

现在要判断有没有不重叠的两个子串。我们贪心地找出每段中最靠前的那个子串和最靠后的那个子串，如果这两个都重叠，那就不可行，缩小 (len)，否则扩大 (len)。

加强版：不重叠出现至少k次的最长串长度

对于这种不重叠问题，较为常见的方法是根据子串在原串中的位置来判断。

同样二分答案，将同一块内所有子串的编号（位置）排个序，然后又知道了串长，可以知道子串的起始位置和终止位置。然后就相当于“选择最多不交线段”的问题了，可以贪心解决。

复杂度 (O(nlog^2n))，但是第二个 (log) 非常小。

有个 (O(nlogn)) 的做法：我们把同一个块内的所有子串在原字符串中打上标记，然后在原串上扫描一遍，贪心选取每种串即可。这样是稳定 (O(nlogn)) 的。

例题：4097. 【GDOI2015】短信加密

最长AA式子串

T121316 最长重复子串

枚举len，每len个点放一个点，则重复子串一定跨越两个点。对于相邻点对，求lcp和lcs，判断。

my record

AABB式的子串个数

看一下例题吧：优秀的拆分

题解的图非常好：题解【P1117优秀的拆分】

这里给出关键部分代码：

int array[N];//array[i]:从i开始向右延伸的"AA"个数 
int dearray[N];//dearray[i]:从i开始向左延伸的"AA"的个数
inline void calc(int pos, int len) {
	int lcp = A.get_lcp(pos + 1, pos + len + 1);
	if (lcp > len - 1)	lcp = len - 1;
	int lcs = B.get_lcp(n - (pos + len) + 1, n - pos + 1);
	if (lcs > len)	lcs = len;
	if (lcs + lcp < len)	return ;
	int chonghe = lcs + lcp - len;
	array[pos - lcs + 1]++;
	array[pos - lcs + 2 + chonghe]--;
	dearray[pos + len + lcp - chonghe]++;
	dearray[pos + len + lcp + 1]--;
}
...
for (register int i = 1; i <= (n >> 1); ++i) {
	for (register int j = i; j + i <= n; j += i) {
		calc(j, i);
	}
}

还是看图理解吧。

AxxxA式（xxx的个数已知）的子串个数

UVA10829 L-Gap Substrings

照样和前两种模型的解决方法类似：枚举A串的长度 (len)，每 (len) 个字符中放一个点。我们的任务是查询第一个A（长度为len）包含某一个点的AxxxA式的串有多少个。

设当前点为(l)，则令(r = l + g + len)，其中 (g) 表示给定的 (x) 的个数，并求出其lcp，lcs（与len取min）然后就要自己动手画图了。推出该AxxxA串的左端点的区间为 ([l - lcs + 1, l + lcp - 1 - len + 1])，即 ([l - lcs + 1, l + lcp - len])，这样的话合法的xxx的个数为 (lcp + lcs - len)。记得答案对0取max（非负）。

my record

结合各种数据结构

结合并查集

典型例题：品酒大会

不说了，满眼都是泪。