题意：
给定一个长度为 n 的字符串，让求出它的第 $k$ 小子串是什么。每次除字符串之外还会给定两个参数 $t $和 $k$ ，$t$ 为 $0$ 则表示不同位置的相同子串算作一个, $t$ 为 $1$ 则表示不同位置的相同子串算作多个。数据范围 $n\le 5*10^5$ $t\in {0,1}$ , $k \le 10^9$.
题解：
后缀自动机板子题。我们知道每一个子串放在sam上跑一定可以走到一个合法节点，反过来说任意一个节点一定代表了一批能走到这儿的子串。那么我们可以想办法把到达每个节点有多少种子串用dag图上dp的方式求出来，然后在t=1的时候，根据sam的性质，给每个dp值再乘以一个 $|endpos|$ 就可以了。学习到的是比我原来板子更快的拓扑排序方式。。。直接用len结果在数组里排序，比起用queue来常数小了很多。另外还纠正了自己的对于sam拓扑序的一个错误认识，他其实无论是slink还是dwag的拓扑序都是一样的，因为无论哪种都一定是从小的子串往大的走。
继续阅读“[SAM][dp][拓扑排序][模板] 洛谷 P3975 TJOI2015 弦论”