第一篇题解说上界是 trie 树大小乘字符集大小的

可为什么不是 $3|\sum s_i|-2$ ？

类似一般 SAM 的证法

对广义 SAM 这个 dag 找出他的最大生成树 这样树边是 $2|\sum s_i|-2$

dag 无返祖边 考虑横叉边

对于一条横叉边 构造树上路径 -> 横叉边 -> 一个后缀所在的节点

由于本质不同后缀至多 $|\sum s_i|$ 个 而 SAM 上一条路径对应一个子串且两两对应的字串不同 所以横叉边至多 $|\sum s_i|$ 条 所以边数最多 $3|\sum s_i|-2$

我觉得没啥问题 然后那个原论文给的反例我没看懂 我觉得建出来边数挺对的/kk