$O(n^2)$，随便水
考虑二分答案，二分答案串在原串中的排名。
考虑如何$check$，从后向前扫每个串，每次在串的前面加入一个字符，如果这个串的字典序>当前串，那么在这个地方断掉。最后检验次数是否小于$k$即可。
对于比较两个串字典序的问题，直接用后缀数组求$lcp$就可以做到$O(1)$比较。
似乎是个套路？考虑枚举长度$L$，每隔$L$设立一个关键点，计算跨过这个关键点的贡献。手模一下可以发现这东西就是$i$与$i+L+m$的$lcs$和$lcp$之和，用后缀数组求出来ST表$O(1)$询问即可。
正解貌似是后缀自动机，在$parent$树上建出虚树，然而直接后缀数组，然后单调栈维护一下就好了。
原文：https://www.cnblogs.com/hzoi-cbx/p/12093683.html