后缀数组、后缀自动机学习笔记（没写完）
后缀数组、后缀自动机学习笔记
后缀数组（SA）
前置知识
倍增、计数排序、基数排序。
后缀数组定义
我们约定字符串 \(s\) 的后缀 \(i\) 指 \(s_{i\dots n}\)。
后缀数组（Suffix Array）主要是两个数组 \(sa\) 和 \(rk\)，\({sa}_i\) 表示后缀排序后第 \(i\) 小的后缀编号，\({rk}_i\) 表示后缀 \(i\) 的排名。
显然，\({sa}_{{rk}_i}={rk}_{{sa}_i}=i\)。
例如对字符串 \(\texttt{aabaaaab}\) 的后缀排序如下：
\[ \begin{array}{c:cccccccc} rk & 4 & 6 & 8 & 1 & 2 & 3 & 5 & 7 \\ s & \texttt{a} & \texttt{a} & \texttt{b} & \texttt{a} & \texttt{a} & \texttt{a} & \texttt{a} & \texttt{b} \\ \hline {sa}_1=4 & \texttt{a} & \texttt{a} & \texttt{a} & \texttt{a} & \texttt{b} & & & \\ {sa}_2=5 & \texttt{a} & \texttt{a} & \texttt{a} & \texttt{b} & & & & \\ {sa}_3=6 & \texttt{a} & \texttt{a} & \texttt{b} & & & & & \\ {sa}_4=1 & \texttt{a} & \texttt{a} & \texttt{b} & \texttt{a} & \texttt{a} & \texttt{a} & \texttt{a} & \texttt{b} \\ {sa}_5=7 & \texttt{a} & \texttt{b} & & & & & & \\ {sa}_6=2 & \texttt{a} & \texttt{b} & \texttt{a} & \texttt{a} & \texttt{a} & \texttt{a} & \texttt{b} \\ {sa}_7=8 & \texttt{b} & & & & & & & \\ {sa}_8=3 & \texttt{b} & \texttt{a} & \texttt{a} & \texttt{a} & \texttt{a} & \texttt{b} & & \\ \end{array} \]
\(\mathcal{O}(n^2\log n)\) 求法
这个求法不用我讲吧，直接对着 string 搞 sort，比较字符串是 \(\mathcal{O}(n)\) 的，所以排序是 \(\mathcal{O}(n^2\log{n})\) 的。
\(\mathcal{O}(n\log^2 n)\) 求法
字符串哈希预处理，然后二分求最长公共前缀。
\(\mathcal{O}(n\log^2 n)\) 求法
我们把 \(s_{n+1\dots\infty}\) 全部填充为 \(-\infty\)。
这个做法需要倍增的思想。
设 \({rk}_{w,i}\) 表示 \(s_{i\dots i+w-1}\) 在 \(\{s_{x\dots x+w-i}\mid x\in[1,n]\}\) 的排名，对于 \(i>n\) 我们认为 \({rk}_{w,i}=-\infty\)。
我们可以首先对每个字符进行排序得到 \({rk}_{1,i}\)，然后考虑怎么利用 \({rk}_{w,i}\) 求出 \({rk}_{2w,i}\)。只要以 \({rk}_{w,i}\) 为第一关键字，以 \({rk}_{w,i+w}\) 为第二关键字排序，就可以求出 \({rk}_{2w,i}\)。
至于为什么？\({rk}_{w,i}\) 包含了 \(s_{i\dots i+w-1}\) 的信息，\({rk}_{w,i+w}\) 包含了 \(s_{i+w\dots i+2w-1}\) 的信息，类似于 ST 表，把它们合并起来就是 \(s_{i\dots i+2w-1}\) 的信息。
\[ \begin{array}{c:cccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ s & \texttt{a} & \texttt{a} & \texttt{b} & \texttt{a} & \texttt{a} & \texttt{a} & \texttt{a} & \texttt{b} \\ \hline rk_{1,i} & 1 & 1 & 2 & 1 & 1 & 1 & 1 & 2 \\ \hdashline \textrm{key} & 1\ 1 & 1\ 2 & 2\ 1 & 1\ 1 & 1\ 1 & 1\ 1 & 1\ 2 & 2\ 0 \\ rk_{2,i} & 1 & 2 & 4 & 1 & 1 & 1 & 2 & 3 \\ \hdashline \textrm{key} & 1\ 4 & 2\ 1 & 4\ 1 & 1\ 1 & 1\ 2 & 1\ 3 & 2\ 0 & 3\ 0 \\ rk_{4,i} & 4 & 6 & 8 & 1 & 2 & 3 & 5 & 7 \\ \hdashline \textrm{key} & 4\ 2 & 6\ 3 & 8\ 5 & 1\ 7 & 2\ 0 & 3\ 0 & 5\ 0 & 7\ 0 \\ rk_{8,i} & 4 & 6 & 8 & 1 & 2 & 3 & 5 & 7 \\ \end{array} \]
如果用 sort 进行排序，时间复杂度为 \(\mathcal{O}(n\log^2 n)\)。
\(\mathcal{O}(n\log n)\) 做法
既然说“如果用 sort 进行排序”，说明可以不用 sort 进行排序，能够做到更优，省掉一只 \(\log\)。
这时候就需要用到前置知识——计数排序、基数排序了。
需要排序的数组是排名，值域显然为 \([1,n]\)，且只有两个关键字，基数排序只需要排序两次，排序的时间复杂度优化为 \(\mathcal{O}(n)\)。
\(\mathcal{O}(n\log n)\) 做法的一些常数优化
（一）如果排名已经互不相同，就没必要继续排序了。例如上表中的 \({rk}_{4,i}\)。
（二）排名数组的值域可能不到 \([1,n]\)，可以记一下具体的值域，计数排序时少循环一些。例如上表中的 \({rk}_{1,i}\) 和 \({rk}_{2,i}\)。
（三）减少不连续内存访问。然而这个我不会。
放一份用了常数优化（一）（二）的代码：
//By: Luogu@rui_er(122461)
#include
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 1e6+5;
char s[N];
int n, sa[N], rk[N], lst[N<<1], id[N], cnt[N];
template void chkmin(T& x, T y) {if(x > y) x = y;}
template void chkmax(T& x, T y) {if(x < y) x = y;}
int main() {
scanf("%s", s+1);
n = strlen(s+1);
int m = 300; // 值域
rep(i, 1, n) ++cnt[rk[i] = s[i]]; // 计数排序基本操作，统计每个数出现次数
rep(i, 1, m) cnt[i] += cnt[i-1]; // 计数排序基本操作，用前缀和求出每个值的排名
per(i, n, 1) sa[cnt[rk[i]]--] = i; // 计数排序基本操作，利用每个值的排名从右往左算每个数排名并赋值，计数排序不熟的话建议手玩一下
for(int w=1,p=0;;w<<=1,m=p) {
// 基数排序按关键字从不重要到重要排序
// 下面三行是对第二关键字的排序，sa[i] 是 i 的第一关键字，id[i] 表示第二关键字排名为 i 的数，第一关键字的位置
p = 0;
per(i, n, n-w+1) id[++p] = i; // 把最后 w 个第二关键字是无穷小的放进来
rep(i, 1, n) if(sa[i] > w) id[++p] = sa[i] - w; // 找第二关键字，如果 sa[i] > w 就可以作为别人的第二关键字，那就把第一关键字的坐标添加进 id 里
// 上面进行了常数优化（二），因为第二关键字的排序不需要使用计数排序
// 下面四行是对第一关键字的排序，使用计数排序，与上面计数排序基本相同，不再解释
memset(cnt, 0, sizeof(cnt));
rep(i, 1, n) ++cnt[rk[id[i]]];
rep(i, 1, m) cnt[i] += cnt[i-1];
per(i, n, 1) sa[cnt[rk[id[i]]]--] = id[i];
memcpy(lst, rk, sizeof(rk)); // 备份一下排名数组，因为下面要修改
p = 0;
rep(i, 1, n) { // 求出每个位置新的排名
if(lst[sa[i]] == lst[sa[i-1]] && lst[sa[i]+w] == lst[sa[i-1]+w]) rk[sa[i]] = p; // 如果与前一名两个关键字都相等，那么它们并列
else rk[sa[i]] = ++p; // 否则排在前一名的后面，即把名次加一
}
if(p == n) { // 常数优化（一），即顺序已经确定不需要继续排序
rep(i, 1, n) sa[rk[i]] = i;
break;
}
}
rep(i, 1, n) printf("%d%c", sa[i], " \n"[i==n]);
return 0;
} 代码加了不少注释，这是无注释代码：
//By: Luogu@rui_er(122461)
#include
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 1e6+5;
char s[N];
int n, sa[N], rk[N], lst[N<<1], id[N], cnt[N];
template void chkmin(T& x, T y) {if(x > y) x = y;}
template void chkmax(T& x, T y) {if(x < y) x = y;}
int main() {
scanf("%s", s+1);
n = strlen(s+1);
int m = 300;
rep(i, 1, n) ++cnt[rk[i] = s[i]];
rep(i, 1, m) cnt[i] += cnt[i-1];
per(i, n, 1) sa[cnt[rk[i]]--] = i;
for(int w=1,p=0;;w<<=1,m=p) {
p = 0;
per(i, n, n-w+1) id[++p] = i;
rep(i, 1, n) if(sa[i] > w) id[++p] = sa[i] - w;
memset(cnt, 0, sizeof(cnt));
rep(i, 1, n) ++cnt[rk[id[i]]];
rep(i, 1, m) cnt[i] += cnt[i-1];
per(i, n, 1) sa[cnt[rk[id[i]]]--] = id[i];
memcpy(lst, rk, sizeof(rk));
p = 0;
rep(i, 1, n) {
if(lst[sa[i]] == lst[sa[i-1]] && lst[sa[i]+w] == lst[sa[i-1]+w]) rk[sa[i]] = p;
else rk[sa[i]] = ++p;
}
if(p == n) {
rep(i, 1, n) sa[rk[i]] = i;
break;
}
}
rep(i, 1, n) printf("%d%c", sa[i], " \n"[i==n]);
return 0;
} \(\mathcal{O}(n)\) 做法
- SA-IS 算法
- DC3 算法
然而一般来讲时间复杂度瓶颈不在后缀排序，而且这两个太毒瘤了，所以不想学。
height 数组
最长公共前缀（LCP）
两个字符串 \(s,t\) 的 LCP 为最大的满足 \(\forall i\in[1,x],s_i=t_i\) 的 \(x\)，显然 \(x\in[0,\min(|s|,|t|)]\)。
height 数组定义
对于字符串 \(s\)，我们称 \(s_{i\dots n}\) 为“后缀 \(i\)”，记 \(lcp(i,j)\) 表示后缀 \(i\) 和后缀 \(j\) 的 LCP，则定义 height 数组满足 \({height}_i=lcp({sa}_{i-1},{sa}_i)\)。特别地，\({height}_1=0\)。
\(\mathcal{O}(n)\) 求 height 数组
引理一：\(lcp(i,j)=\min\{{height}_k\mid {rk}_i < k\le {rk}_j\}\ ({rk}_i < {rk}_j)\)。
感性理解，因为按字典序排列，所以排的越远相似度（LCP）越低。
严格证明可以参考论文。
引理二：\({height}_{{rk}_i}\ge {height}_{{rk}_{i-1}}-1\)。
证明：设 \(h_i={height}_{{rk}_i}\)，即后缀 \(i\) 和排在它前一名的后缀的 LCP，原式化为 \(h_i\ge h_{i-1}-1\)。
设 \({sa}_{{rk}_{i-1}-1}=k\)，即排在后缀 \(i-1\) 前一名的是后缀 \(k\)。
如果 \(h_{i-1}\le 1\)，显然成立。
如果 \(h_{i-1} > 1\)，因为后缀 \(k\) 和后缀 \(i-1\) 的 LCP 大于一，所以第一个字符对字符串大小的比较没有影响，得到后缀 \(k+1\) 排在后缀 \(i\) 前面，且 \(lcp(k+1,i)=h_{i-1}-1\)。根据引理一 \(h_i\ge h_{i-1}-1\) 成立。
综上，\({height}_{{rk}_i}\ge {height}_{{rk}_{i-1}}-1\)。
说了这么多，是时候来讲讲 \(\mathcal{O}(n)\) 求 height 数组的算法了，这个算法就是——暴力。复杂度？根据引理二显然。
代码：
rep(i, 1, n) {
int j = height[rk[i-1]];
if(j) --j;
while(a[i+j] == a[sa[rk[i]-1]+j]) ++j;
height[rk[i]] = j;
}SA 和 height 数组练习题
P3809 【模板】后缀排序、P6456 [COCI2006-2007#5] DVAPUT、P4051 [JSOI2007]字符加密等。
然后 OI Wiki 有不少题。
后缀自动机（SAM）
前置知识
等价类。
zpl 要求我解释解释，那我试试吧。
我们定义一个集合 \(S\) 上的等价关系 \(\sim\)，对于一个元素 \(a\in S\)，所有满足 \(b\in S\) 且 \(a\sim b\) 的元素 \(b\) 都在 \(a\) 的等价类中。
举几个例子：
- \(S\) 是北京市常住人口的集合，定义等价关系 \(\sim\) 为住在同一个区，则所有住在海淀区的人在同一个等价类中，但住在海淀区的人和住在朝阳区的人不在同一个等价类中。
- \(S\) 是整数集合 \(\Z\)，定义等价关系 \(\sim\) 为模 \(2\) 余数相等，则所有奇数在同一个等价类中，所有偶数在同一个等价类中。
- \(S\) 是分数集合 \(\Z\times(\Z\setminus\{0\})\)（也就是有理数集合 \(\Q\) 的分数形式），定义等价关系 \((a,b)\sim(c,d)\) 为 \(ad=bc\)，则所有满足 \(\frac{a}{b}=\frac{c}{d}\) 的分数在同一个等价类中。
定义
下文记 \(\Sigma\) 为字符集。
后缀自动机（Suffix Automaton）是一个字符串所有子串的压缩形式，能解决许多字符串相关问题。
字符串 \(s\) 的 SAM 是接受 \(s\) 所有后缀的最小 DFA（确定性有限状态自动机）。
如果你不知道自动机是啥（看不懂上面那句话），那么可以看下面的解释：
- SAM 是一个 DAG，节点称为状态，边称为转移。
- 图存在源点 \(t_0\)，称为初始状态，从 \(t_0\) 出发可以到达所有节点。
- 有若干个终止状态，满足从 \(t_0\) 出发，经过若干条边走到一个终止状态，则路径上所有转移的字母连起来是 \(s\) 的后缀，\(s\) 的后缀也都可以用这样一条路径表示。
- SAM 是满足前三条性质的节点数最少的自动机。
SAM 包含一个字符串所有子串的信息，任意一条从 \(t_0\) 开始的路径，把转移的字母连起来，都会得到一个 \(s\) 的子串，每个 \(s\) 的子串也可以用这样一条路径表示。我们称这种子串和路径的关系为“对应”，下文可能出现路径对应了子串，或者子串对应了路径，就是这个意思。SAM 中到达一个状态的路径可能不止一条，我们称这个状态对应可以到达它的字符串的集合，这个集合的每个元素对应一条到达这个状态的路径。
我们举个简单的例子，对于字符串 \(\texttt{abbb}\) 建出的 SAM 如下：
根据上面的定义，我们可以说路径 \(t_0\stackrel{\texttt{a}}{\to}1\stackrel{\texttt{b}}{\to}2\stackrel{\texttt{b}}{\to}3\) 对应了子串 \(\texttt{abb}\)。在这个 SAM 中，有两条从 \(t_0\) 到 \(4\) 的路径，也就是说状态 \(4\) 对应了字符串集合 \(\{\texttt{abbb},\texttt{bbb}\}\)。但为什么可以这么对应，这两个字符串有什么共同点呢？我们继续往下讲。
结束位置 \(\textrm{endpos}\)
对于字符串 \(s\) 的所有非空子串 \(t\)，我们记 \(\textrm{endpos}(t)\) 为在 \(s\) 中 \(t\) 的所有结束位置。例如对于字符串 \(\texttt{abcbc}\)，有 \(\textrm{endpos}(\texttt{bc})=\{3,5\}\)。
我们定义集合 \(S\) 为字符串 \(s\) 所有非空子串的集合，定义等价关系 \(\sim\) 为 \(\textrm{endpos}\) 相等，这样字符串 \(s\) 的所有非空子串都可以根据 \(\textrm{endpos}\) 划分为若干等价类。
则 SAM 的每个状态都对应了一个等价类，也就是一个或多个 \(\textrm{endpos}\) 相同的子串。在上面那个例子里，\(\texttt{abbb}\) 和 \(\texttt{bbb}\) 的 \(\textrm{endpos}\) 均为 \(4\)。
根据上面的定义，我们有一些引理：
引理一：字符串 \(s\) 的两个非空子串 \(u,v\) 满足 \(|u|\le |v|\) 且 \(\textrm{endpos}(u)=\textrm{endpos}(v)\)，当且仅当 \(u\) 在 \(s\) 中所有出现位置都是 \(v\) 的后缀。
显然成立。
引理二：字符串 \(s\) 的两个非空子串 \(u,v\) 满足 \(|u|\le |v|\)，则满足：
\[\begin{cases}\textrm{endpos}(u)\cap\textrm{endpos}(v)=\varnothing,&u\textrm{ is not a suffix of } v\\ \textrm{endpos}(v)\subseteq\textrm{endpos}(u),&\textrm{otherwise}\end{cases}\]
证明：若 \(\textrm{endpos}(u)\cap\textrm{endpos}(v)\ne\varnothing\)，则 \(u,v\) 至少一次同时出现，类似于引理一可知 \(u\) 是 \(v\) 后缀，则 \(v\) 每一次出现 \(u\) 都会出现，即 \(\textrm{endpos}(v)\subseteq\textrm{endpos}(u)\)。
引理三：对于一个 \(\textrm{endpos}\) 等价类，不存在两个等长子串；且把属于这一等价类的所有子串按长度递增顺序排序，则前一个子串是后一个子串的后缀，这些子串的长度覆盖一个整数区间 \([x,y]\cap\Z\)。
证明：若等价类中只有一个元素，显然成立。
否则，由引理一，较短子串总是较长子串的真后缀，等价类中没有等长的子串。
记等价类中最长、最短的子串为 \(u,v\)，则 \(x=\textrm{len}(v),y=\textrm{len}(u)\)。考虑长度在 \([x,y]\) 间的 \(u\) 的后缀 \(w\)，由引理一知 \(v\) 是 \(u\) 的后缀，则 \(v\) 是 \(w\) 的一个后缀。由引理二知 \(\textrm{endpos}(v)\subseteq\textrm{endpos}(w)\subseteq\textrm{endpos}(u)\)，又因为 \(\textrm{endpos}(u)=\textrm{endpos}(v)\)，所以 \(\textrm{endpos}(w)=\textrm{endpos}(u)\)，\(w\) 也在这个等价类中。所有长度在 \([x,y]\) 间的 \(u\) 的后缀都在这个等价类中，因此这些子串的长度覆盖整数区间 \([x,y]\cap\Z\)。
后缀链接 \(\textrm{link}\)
咕咕咕。