火萤Ⅳ型，已就位：后缀自动机（SAM）学习笔记

整体结构SAM 的内部包含两套边理解这两套边是掌握 SAM 的关键。第一套边带字符的转移边可以通过类似 Trie 树的方式在这个图上转移但整个图形成了一张有向无环图而不是树。从初始状态出发沿着转移边走经过的边上的字符连起来形成的字符串恰好是原串的某一个子串。并且原串的每个子串都对应这样的一条路径。注意多个不同的子串可能走到同一个状态因此 SAM 可以压缩很多状态。第二套边后缀链接Parent 树后缀链接指向的一个状态其子串是在其它状态中为其后缀且最长的状态。其中每个状态代表一个endpos 等价类即该状态包含的所有子串它们每次出现时的结束位置集合完全相同。随着状态不断迁移到后缀链接位置子串终止位置不变但是长度变小我们发现endpos 必定增多且一定包含原本的 endpos。再反过来思考一下对于一个子串在它的左边添加一个字符这个字符决定了这个子串之后可能出现在哪里对于不同字符对应的位置是不一样的。因此我们把每个后缀链接连边形成一棵树通常称为Parent 树或后缀链接树。那么一个节点的 endpos 集合是其所有子节点 endpos 集合的并集并且子节点之间的 endpos 集合互不相交。当然对于初始状态空串设定 endpos 就是所有位置。对于一个子串在它的前面加上字符的同时在原字符串中仍然存在的方案可能只有一种因此 SAM 会对其进行压缩用 lenlen 表示其最长长度。那么由之前一次次加入字符的角度考虑一个状态代表的子串长度是连续且不重复的并且在长度为 lenlen 之后会产生不同结果或者无法进行那么长度的区间为 (len[fa],len](len[fa],len]。根据我们不断缩短后缀的方式我们可以发现两个状态在 Parent 树上的LCA所代表的最长子串就是这两个状态对应子串的最长公共后缀。构造方法只要我们通过整体结构知道这个 SAM 是需要干什么的要维护怎样的内容构造的方法也就比较好想了。我们按照顺序一个一个加入字符串的节点到自动机中。我们加入一个之后首先考虑保持 Trie 树的结构。那么我们显然需要把所有在上一个加入的字符之后加上一个新的字符需要跳转之前的串的所有的后缀。对于这个后缀没有之后的点为加入的字符的情况那么直接给它加上新的转移点。如果加入所有后缀都没有这个字符那么这个新建节点就是唯一一个可以以这个点为结束位置的直接把后缀链接连到初始位置。否则有一个后缀在前面出现的地方后面有这个字符。比如abceeeab后面加上一个c的话。那么此时ab所代表的子串已经有后面存在c的情况了看看怎么处理。对于不带有c这个字符的转移的直接将这个转移到新建点即可。等处理到后缀ab时这个点已经有这个转移了那么我们这个点就没有必要成为之后的其它后缀的转移点了。所以直接把后缀链接设到这个点的c转移的那个状态就行了因为这是除c外这个字符串中最长的且有下一个c转移的后缀因此就是新字符串的最长后缀。但是这样就正确了吗你迫不及待地拿了一个串abb想要试试。你把最后一个b放上去它的后缀链接连接着上一个b所在的状态。最后得到这样一张图你发现这样好像确实可以从根走到每一个点但是你忘了需要满足每个点代表的子串结束位置要相同我们发现节点 3 同时表示了b和ab两个子串。这种情况下对于上一个b所在的状态会出现它同时代表ab和b两个字符串。但是ab并不是abb的后缀并且两个子串的结束位置完全不同这是为什么我们在走 Trie 树上的边得到的结果并不是我们到哪个节点就表示哪个子串而是根据我们走的路径上有哪些字符所以我们从那个有b转移的地方走了一个b的话形成的新子串长度应该只加一但是由于那个状态还包含了其他更长的子串它的最长长度未必就是多一的。解决方法也很简单我们再克隆一个新状态把它的最长长度设为当前这个点的长度加一即可它的其它信息转移边和后缀链接和原本的这个错误的选择节点一样。我们把新克隆出来的点作为后缀链接指向的节点就行了。这个克隆操作的本质其实是将原本 SAM 压缩的一个状态给重新分成了两个状态这两种状态原本所要维护的东西除了最长长度外完全一致。因此注意要修改之前的一些点让其 Trie 树上的儿子改为这个克隆出来的点比如其中的节点 1因为我们相当于把原本的节点 3 给拆了而对于我们所遍历的后缀在 Trie 树上的结构就是要选择被克隆出来的新节点。得到的结果如图经过复制操作并且对一部分边进行重定向后我们就得到了正确的后缀自动机。这样就完成了整个 SAM 的构造只要理解了 SAM 的整体结构还是比较好理解的。后缀自动机 洛谷 - P3804看看代码可结合注释食用点数、边数、复杂度分析点数SAM 拥有非常优秀的性质它的总点数最多是字符串长度的两倍。这是由于每次只会增加一个点然后可能会克隆一个点所以就是两倍的点数。那么容易得到状态数最多为 22n了。但是实际上界差不多是2−12n−1除了 1n1 的情况外很难达到上界只需要写代码的时候开两倍就行了。边数至于边数考虑起来则比较复杂了。首先考虑所有长度为 len[u]1len[v]len[u]1len[v] 的情况。显然对于每一个状态都只会有一条满足这个性质的边。除了初始状态外所有点的长度都是某个点长度加上一得到的也就是每个除了初始状态外都有一条边。那么结合大部分情况下的点数上界有 2−22n−2 条。然后考虑其它边。这时候有一个非常厉害的性质我们要求从初始位置开始找到必须经过这条转移边的最长路径。由于每个点都是一个点长度加一得到的因此经过这条边的最长路径肯定全部都是加一的路径了。由于之后没有其它状态了所以这一定对应一个这个字符串的后缀。每个子串都对应一个路径所以这种边肯定只会有对应后缀的数量总共有 −1n−1 条。那么总的边数大概就是 3−33n−3 了实际上很多时候只有3−43n−4总之就是差不多 33n非常优秀。时间复杂度讨论时间复杂度的时候我们先假定字符集大小很小可以忽略视为常数不然连边的时间复杂度搞不好还要带一只 log⁡log 。发现时间复杂度的瓶颈肯定在两个 while 循环上。考虑 while 循环会循环几次。我们每次都是在上一次初始的节点开始的。跳一次就是直接到达其后缀链接的位置。我们看看这个后缀链接。我们发现其后缀链接要么是初始位置要么是在上一次遍历到的节点的长度加一处。那么每次都加一但是跳转后缀链接时一定会让长度减小所以总共的时间复杂度是 ()O(n) 的但是其实你开数组的时候就已经给它乘上了一个字符集大小所以还是要注意的可能部分题目需要用 map 来存不然空间给你爆了。广义后缀自动机然而有的时候我们可能需要把多个字符串放入一个 SAM 里面。实际上处理这种问题的方法有很多比如直接在中间插入分隔符但是这样在处理较多字符串时效率较低部分问题需要特判分隔符的影响比较麻烦。对于直接把 lastlast 重新放到初始位置的做法其时间复杂度无法得到保障。为了使时间复杂度仍然被保证我们考虑把相同的字符合在一起进行处理。显然可以构建一个Trie 树这样对于树上的每个节点其儿子所代表的字符都是互不相同的。BFS 遍历 Trie 树。当处理 Trie 节点 u 时我们已经知道了它在 SAM 中对应的状态编号 pos[u]pos[u]也就是插入 u 这个字符序列后的 lastlast。对于 u 的每一个儿子字符 c我们把 lastlast 设置为 pos[u]pos[u] 后再加入字符 cc并把返回的新状态赋值给儿子节点。这样就把相同字符的干扰去掉了由于 Trie 上每个节点的子节点字符互不相同因此在 BFS 建 SAM 时每次 insertinsert 操作面对的 lastlast 状态都不会发生这个字符已经转移过的情况由于不同字符插入同一个 lastlast 再操作上互不干扰保证了总复杂度仍为(∑∣∣)O(∑∣Si​∣)的如果不把字符集大小当成常数那就再乘上不过一般用到的时候都不会很大。因此我们直接 BFS 下去把 lastlast 设为每个点的父亲加入后的 lastlast不断插入即可。注意这里是 BFS 而不是 DFS我们发现如果你继续在之后添加那么之前提到的“由于不同字符插入同一个 lastlast 再操作上互不干扰”这个性质就失效了所以应该使用 BFS 而非 DFS。