SPOJ SUBLEX Lexicographical Substring Search ( 后缀自动机)

2017年11月8日 0 作者 CrazyKK

http://www.spoj.com/problems/SUBLEX/en/

题意:

给一个字符串,每次询问字典序第k大的不重复子串。

思路:

先做个拓扑dp,求出SAM上,一个状态到种态的路径数。

拓扑dp其实就是按照拓扑序的dp啦…

然后从SAM的初始态开始,每次字典序从小到大得贪心寻找。思想类似可持久化线段树求区间第k大。