后缀树的 dfn 是字典序

这个东西十分的深刻，因为有一天我回看 TJOI 弦论代码的时候，我发现后缀树上每个节点明明代表了一类 $\rm endpos$ 集合相同的串，但我们在自动机上跑的时候却没事！

关心自动机结构的时候就不要同时关心后缀树，后缀自动机那么压缩是因为对于那些节点，其后继的状态是完全相同的，所以这就是一个正经的自动机结构，匹配到一个位置意味着可能遇到了上面的任意一个串，所以我们在自动机上进行跑的时候，通常还需要再记录匹配的长度。

$\rm SAM$ 可以利用后缀树的结构实现“删掉首字母”的匹配，具体来说就是删到无法匹配了就跳到后缀树上的父亲。

所以我们可以感受到，后缀树作为一棵压缩 $\rm Trie$ ，我们通常的求法却没有为边求出其代表的串，就失去了一些性质可以利用了。

求出这个当然是好求的，对每个节点任意求出一个出现位置，想求哪个字符都可以求。

所以我们当然也可以利用这个结构来实现“添加首字母”的匹配。

同时，TJOI 弦论也存在一个后缀树的做法，我们建出正串后缀树，则 $\rm dfn$ 就是字典序，求字典序第 $k$ 小的子串就十分简单了，多次询问只需在上面二分。

但在自动机上多次询问字典序第 $k$ 小的路径就不一样了，我们可能需要可持久化平衡树。

当然这个平衡树是不需要截断的，因为 $\rm SAM$ 上一个点出发的路径数等价于向后可能匹配的子串个数，总量是不大的。