111qqz的小窝

老年咸鱼冲锋!

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

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

题意:

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

思路:

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

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

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

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz