悲惨故事 长文警告 关于广义 SAM 的讨论

关于广义 SAM 的讨论

因一次惨痛的教训来写这篇帖子。

今天参加联测时，有一道广义 SAM 裸题，本来随便打打就应该过了，结果没想到因为这道题的写挂，让我发现这辈子之前写过的所有广义 SAM 都是错的，同时也发现网络上一些犯有同样错误的博客以及可视化网站。

考虑如下两个字符串构成的广义后缀自动机：

iod
od

我们可以根据这两个字符串建出如下图所示的 Trie，后缀自动机，和 Parent 树。

Trie 中结点的数字表示这个点对应的后缀自动机上的结点。

然而，有一种不常被注意的错误如下图所示：

这种错误似乎是有些普遍的，我们打开洛谷模板题的第一篇题解，来自 @辰星凌 的博客：

https://www.luogu.com.cn/blog/ChenXingLing/solution-p6139

这篇题解中提到三种建立广义 SAM 的方法，并正确地指出了第二种的错误（这和上面我们看到的等价），但是他在第三种算法中说直接运行普通 SAM 的 extend 函数即可得到正确答案，这是错误的。

我找到了博主的 AC 代码并测试，发现这份代码建出的后缀自动机果然有我上面所说的问题。

https://www.luogu.com.cn/record/36889179

接下来我找到了网上的一些后缀自动机可视化网站，抽选了百度出来的第一个结果，以及我平常用的一个网站，调查结果如下：

上图截自 https://mivik.gitee.io/sam-visualizer/，是正确的广义 SAM。

上图截自 https://yutong.site/sam/，犯了我上面所说的错误。

此外还有一些 SAM 可视化网站，如 http://wenhao801.com:5000/，这个网站在输入 \texttt{od|iod} 后表现正常，但是在输入 \texttt{iod|od} 后输出了错误的后缀自动机，不过它的错误之处是明显的，不是我要讨论的范围。

下面我们简单讨论一下这个错误。

错误在哪里

错误演示中，多了 5,7 两个结点，按说多了两个没有任何作用的结点并不影响正确性，但问题就出在它们对应的是 Trie 上的两个结点，而这两个结点对应的实际上应该分别是 6,8 两个结点。

为什么有这种错误无法发现？

在部分题目中，这样建立后缀自动机并不会影响答案的正确性，例如洛谷模板题：https://www.luogu.com.cn/problem/P6139。

题目要我们求出 n 个串的本质不同子串的并的大小，正常的方法是求出广义 SAM 后统计所有点与父亲的 len 差并求和。

而如果出现这种错误，由于 5,6 两个点的 len 相同（都是 1），同理 7,8 两个点的 len 相同（都是 2），所以这里加的一个 0 并没有影响答案，看上去就仿佛 Trie 左边的两个点对应了 6,8 一样。

那么这有什么关系呢？

关系很大，它影响了 SAM 的基本结构。

SAM 中一个串只能属于一个结点，同时我们不允许一个点和它的 link 指向结点的 len 相同，而上图的错误打破了这种结构。

更严重的是，它影响了子树与后缀关系的判定，只要遇到需要通过子树操作刻画以某个串为后缀的所有串，上面的方法就出锅了，例如我今天做的那道题。

错误如何产生

这一点在上面提到的博客中阐述的比较清楚（只是似乎作者没有意识到 Trie 树做法也有这个问题）。

正常来说，我们进行单串 SAM 的插入字符时，设之前的终止结点为 las，首先我们会将 las 的一段没有对应字符出边的点的对应字符出边修改为我们新建的点 cur。

单串 SAM 情况下，las 本身必定没有出边，因为它的 maxlen 就是之前字符串的长度，无法进行任何扩展。

但广义 SAM 就不一样了，las 可能已经有对应出边，但这是一个不连续转移（len_q>len_{las}+1，q 是 las 出边指向的点），如果按照单串 SAM 的运行规则，我们新建一个 q 的克隆 clone，令它取代原先指向 q 的部分转移，同时令 q 和 cur 的 link 都指向 clone。

发现了吗？问题就出在最后一句。

注意到此时由于 len_{cur}=len_{las}+1=len_{clone}，而所有 q 的信息都到了 clone 上，所以 clone 才是我们真正需要的点，而 cur 是一个与之等价但没有任何信息的空壳！

但如果按照一般 SAM 的写法，我们会直接返回 cur。

如何解决

解决这个问题是简单的，插入时判定 las 是否有出边，如果有，那么就返回 clone，否则才返回 cur。

当然，这样的解决不够漂亮，因为如最上面图中的 5,7 结点还是存在，只是不会影响我们的算法。

真正合理的解释是我们根本不需要建立 clone，只需要把 q 的部分信息转移到 cur 即可。