BZOJ 3998 [TJOI2015] 弦论

发布于 2018-01-04  136 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3998

题意:对于一个给定长度为 N 的字符串,求它的第 K 小子串是什么。


本质相同与否的子串算不算一个其实只影响了 SAM 上 right 集合大小的含义。

直接建 SAM,拓扑 DP 一下,从根开始贪心的 dfs 即可。

发现拓扑序即按照 mx 排序,可以大幅优化常数。一号板子题。

 


一个非常弱的准退役OIER