发现很久不写字符串所有模板都忘了，还是要复习一遍。
SA
后缀排序
令 \(sa_{i}\) 表示排名为 \(i\) 的后缀编号，\(rk_i\) 表示后缀 \(s[i:n]\) 的排名。有两种求法：
- 朴素倍增，时间复杂度 \(\mathcal O(n\log^2 n)\)。
每次更新两个关键字，暴力 sort，重新编号 \(sa\)。
- 基数排序，时间复杂度 \(\mathcal O(n\log n)\)。
令 \(x_i\) 表示编号为 \(i\) 后缀的第一关键字，\(y_i\) 表示第二关键字排名为 \(i\) 的后缀的编号。
for (int i = 1; i <= n; i ++) cnt[x[i] = s[i]] ++;
for (int i = 2; i <= m; i ++) cnt[i] += cnt[i - 1];
for (int i = 1; i <= n; i ++) sa[cnt[x[i]] --] = i;
/* 对 sa[] 赋初值 */
for (int k = 1; k <= n; k <<= 1) {
int tot = 0;
for (int i = n - k + 1; i <= n; i ++) y[++ tot] = i;
for (int i = 1; i <= n; i ++) if (sa[i] > k) y[++ tot] = sa[i] - k;
// 求出 y[]。
// 因为 [n - k + 1, n] 没有第二关键字（就是 0），所以先排在前面。
// 枚举第二关键字 i，如果有对应的第一关键字，放入数组。
for (int i = 1; i <= m; i ++) cnt[i] = 0;
for (int i = 1; i <= n; i ++) cnt[x[i]] ++;
for (int i = 2; i <= m; i ++) cnt[i] += cnt[i - 1];
// 对第一关键字排序。
for (int i = n; i >= 1; i --) sa[cnt[x[y[i]]] --] = y[i];
// 因为第一关键字相同按第二关键字，所以从大往小枚举第二关键字，这样保证能正确排序（这里注意赋值是编号 x[i]）。
for (int i = 1; i <= n; i ++) rx[i] = x[i];
// 存副本，更新。
x[sa[1]] = 1, tot = 1;
for (int i = 2; i <= n; i ++) {
int nw = sa[i], lst = sa[i - 1];
if (rx[nw] == rx[lst] && rx[nw + k] == rx[lst + k])
x[nw] = tot; else x[nw] = ++ tot;
}
// 如果两个关键字都对应相等，则为相同排名。
m = tot;
// 更新桶大小。
}
height 数组
令 \(\operatorname{LCP}(i,j)\) 为 \(s[i:n]\) 和 \(s[j:n]\) 的最长公共前缀，\(\operatorname{height}_{i}\) 表示 \(\operatorname{LCP}(sa_{i-1},sa_i)\)。有个很明显的结论：\(\operatorname{LCP}(i,j)=\min\limits_{k=rk_i+1}^{rk_j}\{\operatorname{height}_{k}\}\)（LCP Theorem）。
我们再引出 \(h_{i}\) 表示 \(\operatorname{height}_{rk_i}\)，引申出了一个结论为 \(h_i\ge h_{i-1}-1\)，可以看图一。
我们发现从 \(k\rightarrow k+1\) 和 \(i-1\rightarrow i\) 刚好是去掉首字母。对于 \(s[k:n]\) 和 \(s[i-1:n]\) 首字母相同的情况，则 \(\operatorname{LCP}(k+1,i)=h_{i-1}-1\)，根据 LCP Theorem，\(h_{i-1}-1\le h_i\)；首字母不同，\(h_{i-1}=0\)，必然成立。
时间复杂度 \(\mathcal O(n)\)。
for (int i = 1; i <= n; i ++) rk[sa[i]] = i;
int lst = 0;
for (int i = 1; i <= n; i ++) {
if (rk[i] == 1) continue;
int j = sa[rk[i] - 1]; lst = max(0, lst - 1);
while(max(i, j) + lst <= n && s[i + lst] == s[j + lst]) lst ++;
he[rk[i]] = lst;
}
应用
- 不同子串个数
\(ans=\dfrac{n(n+1)}{2}-\sum\limits_{i}\operatorname{height}_i\)。
- 最长公共子串
将所有字符串拼接在一起并用字符隔开，求出 \(sa,\operatorname{height}\) 数组，在 \(sa\) 上双指针求出能覆盖所有颜色的区间 \([l,r]\)，答案即为 \(\max\{\operatorname{LCP}(l,r)\}\)，用单调队列可做到 \(\mathcal O(n)\)。
SAM
以下我们研究都相对于字符串 \(s\)。
\(\textsf{endpos}\)
定义 \(\text{endpos}(r)\)（以下简写 \(\text{pos}(r)\)）为 \(r\) 在 \(s\) 中出现的下标集合。
有以下性质：
- 对于 \(\text{pos}(r)=\text{pos}(r')\) 且 \(|r|>|r'|\)，有 \(r'\) 为 \(r\) 的后缀。
- 对于 \(|r|\ge|r'|\)，只有 \(\text{pos}(r)\subseteq \text{pos}(r')\) 或 \(\text{pos}(r)\cap \text{pos}(r')=\varnothing\)。
- 对于同一个 \(\text{endpos}\) 等价类集合 \(s\)，所有 \(\text{pos}(r)=S\) 的 \(r\) 组成的长度 \(|r|\) 集合，刚好为一个区间。
于是我们对于每种 \(\text{pos}\) 集合建一个点 \(x\)，并将每个 \(s\) 的子串放到相应的点中，其中 \(\text{len}_{\max}(x)=\max |s'|\)（以下简写为 \(\text{len}(x)\)），其中对应的字符串为 \(\text{mx}(x)\)。
\(\textsf{link}\)
令 \(\text{link}(x)\) 表示 \(r=\text{mx}(x)\) 最长的后缀 \(r'\) 对应的节点，满足 \(\text{pos}(r')\not=\text{pos}(r)\)。
有以下性质：
- 连接所有 \((\text{link}(x),x)\)，形成一棵树。
- \(\text{len}_{\min}(x)=\text{len}(\text{link}(x))+1\)。
构造 SAM
SAM 为在线构造，时间复杂度为 \(\mathcal O(n)\)，令当前正在插入字符 \(c\)。
- 令上一次的字符串为 \(s'\)，对应的节点为 \(p\)，则 \(s=s'+c\)。新建目前点为 \(np\)。
- 有 \(\text{len}(np)=\text{len}(p)+1\)，迭代 \(np\) 的 \(\text{link}\) 祖先，对于所有没有 \(c\) 边的节点可以将 \(c\) 边连向 \(np\)。
- 决定 \(\text{link}(np)\)
- 若所有祖先都没有 \(c\) 边，则 \(\text{link}(np)=0\)。
- 否则讨论第一个祖先 \(fa\)，\(c\) 边指向的节点 \(q\)。
- 如果 \(\text{len}(fa)+1=\text{len}(q)\)，说明 \(\text{mx}(fa)+c=\text{mx}(q)\)，则所有在 \(q\) 中的字符串为 \(\text{mx}(fa)+c\) 的后缀，此时 \(\text{link}(np)=q\)。
- 否则 \(\text{mx}(q)\) 并不是由 \(\text{mx}(fa)\) 产生的，我们将 \(q\) 拆成两部分（如图二），将属于 \(\text{mx}(fa)\) 产生的部分设为 \(\text{link}(np)\)，和另一部分的 \(\text{link}\)，并将剩余所有的祖先修改 \(c\) 边。
struct SAM {
int lst, tot, cnt[maxn << 1];
SAM () { tot = lst = 1; }
void ins(int c) {
int p = lst, np = lst = ++ tot; g[np].mx = g[p].mx + 1, cnt[np] = 1;
while (p && !g[p].ch[c]) g[p].ch[c] = np, p = g[p].fa;
if (!p) g[np].fa = 1;
else {
int q = g[p].ch[c];
if (g[q].mx == g[p].mx + 1) g[np].fa = q;
else {
int r = ++ tot;
g[r] = g[q], g[r].mx = g[p].mx + 1, g[q].fa = g[np].fa = r;
while (p && g[p].ch[c] == q) g[p].ch[c] = r, p = g[p].fa;
}
}
}