因一次惨痛的教训来写这篇帖子。
今天参加联测时,有一道广义 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/,这个网站在输入 od|iod 后表现正常,但是在输入 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 可能已经有对应出边,但这是一个不连续转移(lenq>lenlas+1,q 是 las 出边指向的点),如果按照单串 SAM 的运行规则,我们新建一个 q 的克隆 clone,令它取代原先指向 q 的部分转移,同时令 q 和 cur 的 link 都指向 clone。
发现了吗?问题就出在最后一句。
注意到此时由于 lencur=lenlas+1=lenclone,而所有 q 的信息都到了 clone 上,所以 clone 才是我们真正需要的点,而 cur 是一个与之等价但没有任何信息的空壳!
但如果按照一般 SAM 的写法,我们会直接返回 cur。
解决这个问题是简单的,插入时判定 las 是否有出边,如果有,那么就返回 clone,否则才返回 cur。
当然,这样的解决不够漂亮,因为如最上面图中的 5,7 结点还是存在,只是不会影响我们的算法。
真正合理的解释是我们根本不需要建立 clone,只需要把 q 的部分信息转移到 cur 即可。