TJOI2015 弦论

弦论

对于一个给定长度为 \(N\) 的字符串，求它的第 \(K\) 小子串。

\(T\) 为 <code>0</code> 则表示不同位置的相同子串算作一个。\(T\) 为 <code>1</code> 则表示不同位置的相同子串算作多个。

\(N \leq 5 \times 10^5, \ T&lt;2, \ K \leq 10^9\)

首先建立SAM，不同字符串对应于不同的从初始节点开始的路径，然后根据题意分类：

t为0则表示不同位置的相同子串算作一个，那么每个状态对应路径的字符串的出现次数只能算作1次。

t为1则表示不同位置的相同子串算作多个，那么每个状态对应路径的字符串的出现次数等于它的end-pos集合大小，基数排序求拓扑序后更新即可。

时间复杂度\(O(|S|)\)

把初始节点设成1，即让<code>last=tot=1</code>会方便许多。