v 表示包含新后缀的节点。如果 a[v].len == a[p].len + 1 ，那这个点就没有比新后缀更长的串，那就可以直接令 a[np].f = v ，就满足 \mathrm{edp}(np)\subseteq{edp}(v) 的条件。否则， \rm edp 不包含 n ，进入情况3。
考虑将 v 分裂，一部分包含比新后缀更长的串，一部分包含比其更短的串和本身。我们复制 v 形成一个新节点叫 nv （a[nv] = a[v]），强行令其最长串为新后缀，所以有 a[nv].len = a[p].len + 1 。然后在刚才停下的终止链中继续跳，把本来属于 v 的对应入边都给 nv ，那一定能从 v 中剔除新后缀，且满足长度连续，即 for (; p && a[p].t[c] == v; p = a[p].f) a[p].t[c] = nv 。现在的 nv 包含原来的 v （因为这玩意更短，限制更小，集合更大），也包含 n ，所以就令 a[v].f = a[np].f = nv 。
这样一个 \rm SAM 就构造完了。
例题
所有例题的代码均省去 \rm SAM 的板子部分，且默认字符集为小写字母。
洛谷 P2408 不同子串个数
给一个长为 n 的字符串，求不同子串个数。（ 1\le n\le 10^5 ）
有一种经典的 \rm SAM 解法。注意到 \rm SAM 的每个节点表示的串没有交集，且一定表示了所有的串。那我们就把所有节点表示的串个数（即这个等价类的大小）加起来就行了。因为有 \min_u=\max_{fa}+1 ，所以答案即为 \sum_{u} (len_u-len_{fa}) 即可。
#include <cstdio>
const int N = 1e5 + 10;
int n, las, tn; char str[N];
struct node{ ... }a[N << 1];
inline void add(int c) { ... }
int main()
{
scanf("%d%s", &n, str); las = tn = 1;
for (int i = 0; i < n; ++i) add(str[i] - 'a');
long long ans = 0;
for (int i = 1; i <= tn; ++i) ans += a[i].len - a[a[i].fa].len;
printf("%lld\n", ans);
return 0;
}
注意到每个节点代表一个 \rm edp 等价类，那显然有 \rm edp 的集合大小（这玩意很常用，后面称为 siz ）就是这点包含的一堆子串在原串中的出现次数。统计 siz 我们可以考虑在 \rm parent 树上面做树形 \rm DP 。首先把每个前缀所属的点 siz 设为 1 ，因为这些点前面无法再加东西了，为 \rm parent 树上的叶子节点。接着树形 \rm DP ，a[u].siz += a[v].siz 即可。（ v 是 u 的子节点 ）。我们还维护了最长串长度 len ，统计 \max_u[u.siz>1](u.siz\times u.len) 即可。
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
const int N = 2e6 + 10; using std::max;
int n, las, tn; char str[N]; long long ans;
std::vector<int> g[N];
struct node{ int ..., siz; }a[N << 1];
inline void add(int c) {...}
void dfs(int u)
{
for (unsigned i = 0; i < g[u].size(); ++i)
{
dfs(g[u][i]);
a[u].siz += a[g[u][i]].siz;
}
if (a[u].siz > 1) ans = max(ans, 1ll * a[u].siz * a[u].len);
}
int main()
{
scanf("%s", str); las = tn = 1; n = strlen(str);
for (int i = 0; i < n; ++i) add(str[i] - 'a');
for (int i = 0, p = 1; i < n; ++i)
{
p = a[p].t[str[i] - 'a'];
a[p].siz = 1;
}
for (int i = 2; i <= tn; ++i) g[a[i].fa].push_back(i);
dfs(1);
printf("%lld\n", ans);
return 0;
}
CF802I Fake News (hard)
与上文算法类似，只是需要计算的变成了 $\sum_{u} u.siz^2(u.len-fa.len)$ 。
#### 洛谷 P3975 [TJOI2015] 弦论
给定一个长度为 $n$ 的字符串，求出它的第 $k$ 小子串。给定一个参数 $t$ ，如果 $t=1$ ，则不同位置的相同字串算作多个；如果 $t=0$ ，则不同位置的相同子串算作一个。（ $1\le n\le5\times10^5,1\le k\le10^9$ ）
这个有点类似于在 $\rm BST$ 上面求第 $k$ 大数的算法。对于一个点连出去的所有 $26$ 个出边来说，走尽量大的第 $i$ 条边，收集这条出边对应的字符，减去前 $i-1$ 条边的 $siz$ ，和这个点的子串个数，这样不断走直到 $k=0$ ，收集到的所有字符合起来就是待求的字符串。问题就落在了如何求 $siz$ 上。我们注意到 $siz_u$ 在这里的意义是从 $u$ 出发的所有字符串个数（包括从 $u$ 到 $u$ ），而这个可以通过在 $\rm parent$ 树上树形 $\rm DP$ 求出。为了区分 $edp$ 的集合大小与这个 $siz$ ，我们称这个 $siz$ 为 $f$ 吧。那如果 $t=1$ ， $f_u=siz_u+\sum_{i=1}^{26}f_{son_{u,i}}$ ，如果 $t=0$ ， $f_u=1+\sum_{i=1}^{26}f_{son_{u,i}}$ ，区别在于重复的子串算 $1$ 还是算不同的。而如果 $t=0$ ，则应该有 $siz_u=1$ ，因为不同的子串算 $1$ 个。我们注意到一个节点不能重复计算，那就打个 $vis$ 标签就行了。
这样我们就几乎做完了，但还有个细节需要处理。就是对于 $f_1$ 来说，如果从 $1$ 到 $1$ 则得到的是空串，不应被统计，所以要把 $f_1$ 的值减一。而对于 $f_u(u\neq 1)$ 来说，从 $u$ 到 $u$ 表示在 $u$ 处停下，不能减一。最终复杂度 $\mathcal{O}(n)$ 。
```cpp
#include <cstdio>
#include <cstring>
#include <vector>
typedef long long ll;
const int N = 1e6 + 10; std::vector<int> g[N];
struct node{ ... }a[N];
int vis[N], n, tn, las, t, k, tp; char str[N], ans[N]; ll f[N];
inline void add(int c) { ... }
void dfs(int u)
{
for (int i = 0; i < g[u].size(); ++i)
{
dfs(g[u][i]);
a[u].siz += a[g[u][i]].siz;
}
}
void dp(int u)
{
if (vis[u]) return ; vis[u] = 1;
f[u] = t ? a[u].siz : a[u].siz = 1;
for (int i = 0, v; i < 26; ++i)
if (v = a[u].t[i]) dp(v), f[u] += f[v];
}
int main()
{
scanf("%s%d%d", str + 1, &t, &k);
n = strlen(str + 1); las = tn = 1;
for (int i = 1; i <= n; ++i) add(str[i] - 'a');
for (int i = 1, p = 1; i <= n; ++i)
{
p = a[p].t[str[i] - 'a'];
a[p].siz = 1;
}
for (int i = 2; i <= tn; ++i) g[a[i].fa].push_back(i);
dfs(1); dp(1); int x = 1; --f[x];
if (f[x] < k) { printf("-1\n"); return 0; }
while (k > 0)
{
for (int i = 0, v; i < 26; ++i)
{
v = a[x].t[i];
if (k > f[v]) k -= f[v];
else
{
x = v; k -= a[x].siz;
ans[tp++] = i + 'a';
break;
}
}
}
ans[tp++] = '\0';
printf("%s\n", ans);
return 0;
}
```
#### 洛谷 SP1812 LCS2 - 多串最长公共子串
给 $n$ 个字符串 $S_i$，求它们的最长公共子串。（ $1\le n\le10,1\le|S_i|\le10^5$ ）
首先考虑两个串的情况。我们发现 $\rm SAM$ 与AC自动机非常相似，甚至 $\rm SAM$ 完全可以理解为把某个串的所有子串建立AC自动机得到的自动机。那既然这样匹配的时候我们把 $\rm SAM$ 当AC自动机用就好了嘛。首先我们对于 $S_2$ 设一个数组叫 $slen$ ，$slen_i$ 表示 $S_1$ 中 $[i-slen_i+1,i]$ 范围内的子串在 $S_2$ 中出现过，即以 $i$ 结尾的位置的最长匹配长度。那最后答案就是 $\max\{slen\}$ 。那这样就可以算了，建立起来 $S_1$ 的 $\rm SAM$ ，然后用 $S_2$ 一点点在上面匹配（增量法），如果当前节点有对应出边就匹配长度加 $1$ ，否则就一直跳 `f` 直到有出边，匹配长度就是该点的 $len+1$ 。而如果回到根都无法匹配长度就为 $0$ 。
那多个跟两个也类似，我们把 $S_1$ 当作匹配串，把其余的串建立起 $\rm SAM$ 。用第一个串在每个 $\rm SAM$ 上匹配，$slen$ 对当前长度取 $\min$ 。最后答案就是 $\max\{slen\}$ 。时间复杂度 $\mathcal{O}(n|S_i|)$ 。
```cpp
#include <cstdio>
#include <cstring>
template <typename T>
inline T min(const T& t1, const T& t2) { return t1 < t2 ? t1 : t2; }
template <typename T>
inline T max(const T& t1, const T& t2) { return t1 > t2 ? t1 : t2; }
const int N = 2e5 + 10;
char str[N], tmp[N]; int top, n, ans, slen[N];
//因为要建立10个，封装结构体比较方便
struct SAM
{
struct node { ... }a[N];
int tn, las;
SAM(int tn = 1, int las = 1) : tn(tn), las(las) {}
void add(int c) { ... }
void insert(char* str, int n) { for (int i = 1; i <= n; ++i) add(str[i] - 'a'); }
}sam[11];
int main()
{
scanf("%s", str + 1); n = strlen(str + 1);
while (~scanf("%s", tmp + 1))
sam[++top].insert(tmp, strlen(tmp + 1));
memset(slen, 0x7f, sizeof slen);
for (int k = 1; k <= top; ++k)
{
int p = 1, plen = 0;
for (int i = 1; i <= n; ++i)
{
int c = str[i] - 'a';
if (!sam[k].a[p].t[c])
{
while (p != 1 && !sam[k].a[p].t[c]) p = sam[k].a[p].f;
plen = sam[k].a[p].len;
}
if (sam[k].a[p].t[c]) { p = sam[k].a[p].t[c]; ++plen; }
slen[i] = min(slen[i], plen);
}
}
for (int i = 1; i <= n; ++i) ans = max(ans, slen[i]);
printf("%d", ans);
return 0;
}
```
#### 洛谷 P6640 [BJOI2020] 封印
给出两个字符串 $s,t$ ，$q$ 次询问，每次询问 $s[l...r]$ 和 $t$ 的最长公共子串长度。（ $1\le |s|,|t|\le2\times10^5,1\le q\le2\times10^5$ ）
先用 $t$ 在 $s$ 的 $\rm SAM$ 上跑一遍匹配，求出 $slen$ 。接着我们注意到答案其实就是 $\max_{i=l}^r\min(slen_i,i-l+1)$ 。里面的 $\min$ 很烦人，考虑去掉。当 $slen_i\le i-l+1$ 时，我们有 $i-slen_i+1\ge l$ ，注意到左边单调不减（因为 $i$ 每次 $+1$ ，而 $slen_i$ 最多 $+1$），那就可以考虑二分。二分出一个 $pos$ 满足对于区间 $[l,pos - 1]$ ，有 $i-l+1>slen_i$ ，而对于 $[pos,r]$ ，有 $slen_i\ge i-l+1$ 。最终答案就是 $\max(\max_{i=pos}^r slen_i,pos-l)$ ，前一项可以用ST表 $\mathcal{O}(1)$ 求出。最终复杂度 $\mathcal{O}(n\log n)$ 。
#### 洛谷 CF235C Cyclical Quest
给出一个文本串 $S$ 和 $n$ 个询问串 $T$，问每个询问串的所有本质不同循环同构在主串中出现的次数总和。（ $1\le n\le10^5,1\le |S|\le10^6,\sum|T|\le10^6$ ）
首先先把原串跟文本串匹配一遍。循环同构就行把第一个字符拿去放到后面，也就把第一个删掉，然后加上一个。如果这个串压根就没有完整出现，就不考虑删除操作了；否则`--len` （ `len` 为该串的长度），如果删了之后 $len$ 不在当前节点区间 $(fa.len,u.len]$ 里面了就跳 `f` （删字符其实就是 `f` 到 `u` 在前面加一个字符的过程反过来）。加字符的操作就跟一开始的匹配操作差不多。最终答案就是匹配到的所有节点的 $siz$ 加在一起。因为要求本质不同，如果匹配到同一个节点贡献只算一次，打 $vis$ 标记实现就好。
#### 洛谷 P4248 [AHOI2013] 差异
给定一个长度为 $n$ 的字符串 $S$ ，令 $T_i$ 表示它从第 $i$ 个字符开始的后缀。求：$\sum_{i\le i<j\le n} len(T_i)+len(T_j)-2\times lcp(T_i,T_j)$ 。其中 $len(a)$ 表示字符串 $a$ 的长度，$lcp(a,b)$ 表示字符串 $a$ 和字符串 $b$ 的最长公共前缀。（ $2\le n\le5\times10^5$ ）
把式子变一变，$\sum_{i\le i<j\le n} len(T_i)+len(T_j)-2\sum_{i\le i<j\le n}lcp(T_i,T_j)$ 。我们发现前面的是定值，它等于 $\sum_{i=1}^n\sum_{j=i+1}^n(i+j)=\sum_{i=1}^n\sum_{j=i+1}^ni+\sum_{i=1}^n\sum_{j=i+1}^nj=\sum_{i=1}^ni(n-i)+\sum_{j=1}^n\sum_{i=1}^nj[j>i]=\sum_{i=1}^ni(n-i)+\sum_{j=1}^n\sum_{i=1}^{j-1}j=\sum_{i=1}^ni(n-i)+\sum_{i=1}^ni(i-1)=(n-1)\sum_{i=1}^n=\dfrac{n(n-1)(n+1)}{2}
问题就落在了求两两后缀的 lcp 和，这玩意一看就很后缀树（就是后缀树上两两叶子节点的 lca 深度总和）。但这是 \rm SAM 专题肯定要用 \rm SAM 。但是后缀树写起来....嗯，肯定是不如 \rm SAM 简洁好写的。这里只给出结论，证明不会：反串的 \rm SAM 的 \rm parent 树就是后缀树。那就完事了，构造出来后缀树后 \rm DFS 一遍就好。每个点的贡献分为两部分：一个是两个在不同子树的节点以它作为 lca ，那就是 \sum_{v\in \{son_u\}}siz_v\times (siz_u-siz_v)\times len_u ；一个是它自己和子树内的节点以它作为 lca ，设 s 为并入子节点前的 siz_u ，那这部分的贡献就为 s(siz_u-s)\times len_u 。最终复杂度 \mathcal{O}(n) 。
#include <cstdio>
#include <vector>
#include <cstring>
const int N = 1e6 + 10;
struct node{ ... }a[N];
int tn, las, n; char str[N];
inline void add(int c) { ... }
long long sum; int siz[N];
std::vector<int> g[N];
void dfs(int u)
{
int s = siz[u];
for (int i = 0; i < g[u].size(); ++i)
{
dfs(g[u][i]);
siz[u] += siz[g[u][i]];
}
for (int i = 0; i < g[u].size(); ++i)
sum += 1ll * siz[g[u][i]] * (siz[u] - siz[g[u][i]]) * a[u].len;
sum += 1ll * s * (siz[u] - s) * a[u].len;
}
int main()
{
scanf("%s", str + 1); n = strlen(str + 1);
las = tn = 1;
for (int i = n; i > 0; --i) add(str[i] - 'a');
for (int i = n, p = 1; i > 0; --i)
{
p = a[p].t[str[i] - 'a'];
siz[p] = 1;
}
for (int i = 2; i <= tn; ++i) g[a[i].f].push_back(i);
dfs(1);
printf("%lld\n", 1ll * (n - 1) * n * (n + 1) / 2 - sum);
return 0;
}
洛谷 P6139 【模板】广义后缀自动机（广义 SAM）
给 n 个字符串 s_1,s_2,\cdot\cdot\cdot,s_n ，求本质不同子串个数。（不含空串）（ 1\le n\le 4\times 10^5,1\le\sum_i|s_i|\le10^6 ）
又是一个只会结论不会证明的算法/kk。广义 \rm SAM 识别多个串的所有子串的自动机。这玩意有很多做法，正统的做法应该在 \rm Trie 树上搞，但我只会最简单的。就是加入每一个串以前把 las 设为 1 就好了。那这题就简单了，建立起广义 \rm SAM 后统计 \sum_u (u.len-fa.len) 即可。
#include <cstdio>
#include <cstring>
const int N = 2e6 + 10;
int n, las, tn; char str[N]; long long ans;
struct node{ ... }a[N];
inline void add(int c)
{
...
ans += a[np].len - a[a[np].f].len;
}
int main()
{
int q; scanf("%d", &q); las = tn = 1;
for (int i = 1; i <= q; ++i)
{
scanf("%s", str + 1);
n = strlen(str + 1); las = 1;
for (int i = 1; i <= n; ++i) add(str[i] - 'a');
}
printf("%lld\n", ans);
return 0;
}
其实可以 \rm SAM 搞，但可以广义 \rm SAM 瞎搞，为什么要用复杂的 \rm SAM （bushi。建立起两个串的广义 \rm SAM ，并统计第一个串对应的 siz_0 和第二个串对应的 siz_1 。最后就对每个节点统计 \sum_u (u.len-fa.len)siz_{u,0}siz_{u,1} 即可（乘法原理）。
注意到如果 l=1,r=|S| ，即不存在限制，那就存在一个显而易见的贪心算法。我们先建立起 S 的 \rm SAM ，然后让 T 在 S 上面跑匹配。现在假设在 T_p 无法匹配，那就找一个大于当前 T_p 的字符放在串尾即可。但会出现一个问题，假如所有的候选字符全都小于 T_p ，那就只好去上一位看看有没有大于 T_{p-1} 的，如果都到源点了还没方案输出 -1 即可。复杂度就为 \mathcal{O}(|S|+26\sum|T|) 。
接下来考虑限制。注意到如果我们能构造出 S[l..r] 的 \rm SAM ，那就可以套用上面的贪心。但很明显不可能每次重构，那样复杂度直接爆炸。我们还是先建立起 S 的 \rm SAM ，然后对于每次操作，我们删去所有不包含任意一个 S[l..r] 子串的点及其相关的边，那就得到了 S[l..r] 的 \rm SAM 。这虽然不敢保证点数边数是 \mathcal{O}(n) 的，但至少是合法的，包含所有子串。