首页 > 题解 > bzoj 3998 [TJOI2015]弦论

bzoj 3998 [TJOI2015]弦论

Description

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

Input

第一行是一个仅由小写英文字母构成的字符串S

第二行为两个整数T和K,T为0则表示不同位置的相同子串算作一个。T=1则表示不同位置的相同子串算作多个。K的意义如题所述。

Output

输出仅一行,为一个数字串,为第K小的子串。如果子串数目不足K个,则输出-1

Sample Input

aabc

0 3

Sample Output

aab

HINT

N<=5*10^5

T< 2

K < =10^9

题解

先对这个串建个SAM,再对所有节点按照max排下序。这样就可以从长到短地总结答案。

首先对每个节点维护一个当前节点所占的子串个数。假如t=1就按照Parent树里从叶子节点一层一层往上推的顺序,计算每个串出现的次数。t=0就不用管,直接设成1

这样就可以维护出每个节点往后推会有多少个串。。(直接加起来

然后在SAM上按照字典序往下匹配就可以了


1 COMMENT

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×