【bzoj3998】[TJOI2015]弦论

2015年4月22日3,8606

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

题解

日常orz PoPoQQQ大爷的时候发现了这道裸题。。。
建出自动机求K大。。。没了。。。
T=0 除了根以外的状态都代表1个串
T=1 每个状态fail子树结束结点个数即为串的个数
交错代码wa了一发。。。
大爷说卡常数。?好像没发现。。。
要是比赛看到这种题不是爽的飞起。。。

 

 

  • minitotoro2015年5月6日 下午7:56 回复

    黄学长,求问这个题T=1情况怎么用后缀数组做>_<

    #1  
    • hzwer2015年5月6日 下午8:32 回复
      admin

      求一下每个串是往后多少个串的前缀,这个可以在单调栈上二分,然后应该会做了吧

      #11
  • kj9907032015年8月21日 下午4:47 回复

    扑通扑通跪下来,千古神犇黄哲威

    #2  
  • ez_cjb2015年8月21日 下午4:48 回复

    扑通扑通跪下来,千古神犇黄哲威

    #3  
  • Groot2016年1月10日 下午8:01 回复

    原来对mx[]排序后可以得到自动机和后缀树的拓扑序。怪不得没被卡常数。

    #4  
  • 蒟蒻konjac2017年3月24日 下午2:28 回复

    扑通扑通跪下来,千古神犇黄哲威

    #5