后缀数组
1. 简介
后缀数组是处理字符串的一种强有力工具，高效而且容易编程实现，可应用于求字符串的多种子串问题中，可谓处理字符串的一大利器。
2. 思想
2.1 子串
字符串 S 的子串s[i..j], \ i \leq j表示串S 中从第 i 个字符到第 j个字符形成的字符串。
2.1.1 重复子串
字符串 s在字符串 S中至少出现两次，则称 s 为 S 的重复子串。
- 可重叠重复子串：即重复子串间可以重叠部分子字符串。
- 不可重叠重复子串：即重复子串间不可以有部分重叠的子字符串。
2.1.2 回文子串
字符串 S 的子串 s满足 inverse(s)=s ，则称 s 为 S的回文子串。
2.1.3 公共子串
如果字符串s 同时出现在字符串 SA 和 SB 中，则称字符串s 为字符串 SA 和 SB 的公共子串。
2.2 前缀 & 后缀
前缀是指从串开头到第 i个字符形成的特殊子串，字符串 S 以第 i个字符结尾的前缀表示为 prefix(i)。类似地，后缀是指从第 i 个字符开始到串结尾形成的特殊子串，字符串 S 以第 i 个字符开始的后缀表示为 suffix(i)。
2.3 后缀数组
后缀数组 sa保存的是字符串 S 的 n个后缀（n 为字符串 S 的长度）从小到大排好序后的后缀开头字符在 S 中的下表位置。即 sa[i]表示排名第 i大的后缀的首字符位置。
2.4 名次数组
名次数组 rk 保存的是后缀 suffix(i) 排序后的排名。
【注】 易知后缀数组 sa和 rk满足 sa[rk[i]] = i , \ rk[sa[i]] = i 。故已知其中一者，可以在 O(n)时间内求出另一者。
2.5 高度数组
高度数组 height保存的是排名相邻的两个后缀的最长公共前缀，即height[i] = suffix(sa[i-1]) 和 suffix(sa[i])的最长公共前缀。
- 对于 j和 k，设 rk[j] \lt rk[k] ，则有性质：suffix(j)和 suffix(k)的最长公共前缀为 height[rk[j]+1],height[rk[j]+2],\cdots,height[rk[k]] 中的最小值。
- 定义 h 数组：h[i] = height[rk[i]] 则有性质： h[i] \geq h[i-1] - 1 。
证明 h[i-1] = height[rk[i-1]] 是 suffix(sa[rk[i-1]-1])和 suffix(sa[rk[i-1]])的最长公共前缀，不妨设 s\begin{array}{c} suffix(sa[rk[i-1]-1]) = aAB \\ suffix(sa[rk[i-1]]) = aAC \end{array}
则 h[i-1] = |aA|且 suffix(sa[rk[i-1]-1]) 排在suffix(sa[rk[i-1]])前面。又 \begin{array}{c} sa[rk[i]] = i = i-1 + 1 = sa[rk[i-1]] + 1 \end{array}
故 suffix(sa[rk[i]]) = AC。又 \begin{array}{c} suffix(sa[rk[i-1]-1]+1) = AB \end{array}
故此二者的最长公共前缀为 \begin{array}{c} |A| = h[i-1] - 1 \end{array}
且因为suffix(sa[rk[i-1]-1]) 排在 suffix(sa[rk[i-1]]) 前面，故 suffix(sa[rk[i-1]-1]+1)排在 suffix(sa[rk[i-1]]+1) = suffix(sa[rk[i]]) 前面。根据上一个性质可知，后缀 AC和 AB的最长公共前缀为排名在二者之间的后缀与后缀 AB 的最长公共前缀的最小值，即 \begin{array}{c} h[i-1] - 1 \leq height[rk[i]] = h[i] \end{array}
证毕。
3. 实现
3.1 求后缀数组
- 倍增法（复杂度O(n \lg n) 用倍增的方法对每个字符开始的长度为 2^k的子字符串进行排序。然后合并相邻两个子字符串时将前后两个子字符串的排名看作是两个数位，利用基数排序进行排序，得到以每个字符开始的长度为2^{k+1} 的子字符串的排名，以此类推。直到当2^k \gt n时，每个字符开始的长度为 2^k的子字符串便相当于所有的后缀，即得到最终的后缀数组。
【注】具体实现细节参考下文中的代码。
- DC3 算法（复杂度 O(n)
3.2 求高度数组
利用高度数组的性质，求 h[i] 时，由于 h[i] \geq h[i-1] - 1 ，即 suffix(sa[rk[i]])和 suffix(sa[rk[i]-1])的最长公共前缀至少为h[i-1]-1，故可以直接根据上一步计算出的h[i-1]，然后直接从 str[sa[rk[i]]+h[i-1]-1]与 str[sa[rk[i]-1]+rk[i]-1]处开始继续往后枚举，判断是否还有公共部分。
【注】具体实现细节参考下文中的代码。
4. 模板
4.1 倍增法
#include <bits/stdc++.h>
using namespace std;
#ifndef _SUFFIXARRAY_
#define _SUFFIXARRAY_
#define ll int
#define MAXN 1200000
#define MAXCNT 130
// 后缀数组（倍增算法）
//【注】考虑字符串包括最后的 '\0' 在内
// 故后缀数组大小为字符串长度 + 1
// 实际使用后缀数组 sa 需从 1 开始
// 因为显然后缀 '\0' 排名为首 0
struct SuffixArray {
// 倍增算法计算后缀数组
ll n; // 字符串长度 + 1
ll sa[MAXN]; // 后缀数组
ll rk[MAXN]; // 名次数组
ll ssa[MAXN]; // 保留后缀数组
ll srk[MAXN]; // 保留名次数组
ll cnt[MAXCNT]; // 计数数组
ll height[MAXN];// 排名相邻的两个后缀的最长公共前缀
// 倍增法计算后缀数组
void doubling(char *str, ll m) {
ll i, j, k;
// 使用指针方便交换数组
ll *prk = rk, *psrk = srk;
// 将字符串结束符 '\0' 也算在长度中，有利于后续处理
// 即 str[n-1] = '\0'
n = strlen(str) + 1;
// 初始基数排序
for(i = 0; i < m; ++i) cnt[i] = 0;
for(i = 0; i < n; ++i) ++cnt[prk[i] = str[i]];
for(i = 1; i < m; ++i) cnt[i] += cnt[i-1];
for(i = n-1; ~i; --i) sa[--cnt[str[i]]] = i;
// 后续基数排序
for(j = 1, k = 1; k < n; j <<= 1, m = k) {
// 根据第二关键字（后半段子串上一次基数排序的排名）进行基数排序
// 长度不足 j 的子串第二关键字为 0 ，故排到最前面
for(i = n-j, k = 0; i < n; ++i) ssa[k++] = i;
// 长度恰为 j 的子串，其第二关键字必定大于 j
// 即排名小于 j 的上一轮子串必定不能作为此轮子串的第二关键字
// sa[i] - j 即以 sa[i] 结尾的长度为 j 的子串的首字母
for(i = 0; i < n; ++i) if(sa[i] >= j) ssa[k++] = sa[i] - j;
// 根据第一关键字（前半段子串上一次基数排序的排名）进行基数排序
// 保存此轮排序涉及到的第一关键字，减少不连续内存访问
for(i = 0; i < n; ++i) psrk[i] = prk[ssa[i]];
for(i = 0; i < m; ++i) cnt[i] = 0;
for(i = 0; i < n; ++i) ++cnt[psrk[i]];
for(i = 1; i < m; ++i) cnt[i] += cnt[i-1];
for(i = n-1; ~i; --i) sa[--cnt[psrk[i]]] = ssa[i];
// 计算 rk 数组
swap(prk, psrk);
// 最大的排名保存在 k 中，优化基数排序的值域范围
// 当 2*j > n 时，所有后缀的排名没有相同的，此时 k = n（退出最外层循环）
for(prk[sa[0]] = 0, k = 1, i = 1; i < n; ++i) {
// 由于 str[n-1] = '\0' 故 psrk[sa[i-1]]==psrk[sa[i]] 时：
// str[n-1] = '\0' 不会在 suffix(sa[i-1]) 和 suffix(sa[i]) 中
// 这样保证了 sa[i-1]+j < n 且 sa[i]+j < n
// 即访问 psrk 数组时不会越界
// 因为 psrk 数组界外值都为零，若越界，相当于排名为 0 的后缀，将导致错误
// 这便是开头将字符串末尾 '\0' 算作字符串一部分的原因
prk[sa[i]] = (psrk[sa[i-1]]==psrk[sa[i]] && psrk[sa[i-1]+j]==psrk[sa[i]+j]) ? k-1 : k++;
}
}
}
// 计算后缀最长公共前缀
void generateHeight(char *str) {
ll i, j, k = 0;
// 根据计算出的后缀数组 sa 计算名次数组 rk
// doubling 函数中并不一定计算出了 rk
// 因为 prk 可能指向的是 srk
for(i = 0; i < n; ++i) rk[sa[i]] = i;
// 暴力求解高度数组
// 利用高度数组的性质 h[i] = height[rk[i]] >= h[i-1] - 1
// 计算 h[i] 时直接从 h[i-1] - 1 公共前缀处开始枚举，判断是否还有公共部分
// 由于 str[n-1] = '\0'，rk[n-1] = 0，height[0] 没有意义
// 故不用计算 height[rk[n-1]] = height[0]
// 由于 k-- 最多执行 n-1 次，且最长公共前缀 k < n-1
// 因为 '\0' 不可能是公共前缀的一部分
// 故复杂度最多为 O(2n-3)
for(i = 0; i < n-1; height[rk[i++]] = k)
for(k?k--:0, j = sa[rk[i]-1]; str[i+k] == str[j+k]; ++k);
}
};
#endif