后缀自动机是一种DFN，维护了字符串中所有子串的信息。
对于后缀自动机的fa树，维护的内容本质上是不同串之间 的关系。可以发现，任意两个节点之间的 ，满足 或者 。它们之间的关系形成一棵树。
在后缀自动机中动态插入节点的过程，本质上是加入一个新的endpos集的过程。如果该字符此前从未出现过，那么就对于 之前的所有后缀字符串，它们的 集合都是相同的。如果出现过，那么就要考虑与之合并的问题。
我们考虑合并时刻的情况。当前的节点 有 的转移。说明从 位置的长度为 的后缀都有经过 的转移， 的后缀都没有。
我们考虑对于 节点加入 字符。那么这种转移下的子串满足 。
假设 ，如果 ，那么就可以将 与 直接连边，相当于向 集合中加入 位置。反之的话，相当于要新增一个 的节点，这一节点的 集是 和 的并。对于 和 的父亲节点，转移到 的转移应该改为转移到 的转移，因为新节点实质上是封装了原来节点小于等于 部分的状态，而这部分的状态恰好是 和 的父亲节点们的转移目标。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| namespace SAM {
int fa[N << 1], nxt[N << 1][26], len[N << 1], sz[N << 1];
int samn = 0, tmpend = 0;
void init() {
fa[0] = -1;
}
void build(int key) {
int x = ++samn, u = tmpend;
len[x] = len[u] + 1, sz[x] = 1;
while (u != -1 && !nxt[u][key]) nxt[u][key] = x, u = fa[u];
if (u == -1) fa[x] = 0;
else {
int v = nxt[u][key];
if (len[v] == len[u] + 1) fa[x] = v;
else {
int w = ++samn;
for (int i = 0; i < 26; ++i) nxt[w][i] = nxt[v][i];
fa[w] = fa[v], len[w] = len[u] + 1, sz[w] = 0;
fa[v] = fa[x] = w;
while (u != -1 && nxt[u][key] == v) nxt[u][key] = w, u = fa[u];
}
}
tmpend = x;
}
}
|
例题：动态维护字典序最大的子串。
我们考虑在SAM上对字典序最大的子串对应的状态位置打上 。我们在动态加点的过程中，看是否会修改 位置的最大子串值。可以发现，对于fa树上的有 标记的位置，越高的串肯定比越低的串更优。因此我们只要维护最深位置的节点即可。
接下来考虑 的节点对答案的贡献。如果 节点有 标记或者 及其父亲节点中有 标记，那么本来应该转移到 的路径仍然会被转移到 造成答案错误。因此虽然 节点没有直接对修改起到贡献，但是要使用它去替换 节点在答案路径中的作用。
因此解决这种动态维护的问题，我们首先需要考虑的是新添加节点对于答案的贡献，之后还不能忽视 操作对于答案的影响。
