某岛

… : "…アッカリ~ン . .. . " .. .
August 8, 2014

SPOJ 7258. Lexicographical Substring Search

http://vjudge.net/problem/viewProblem.action?id=28015

Brief description:

求给定字符串,字典序第 kth 大的子串(重复的算一个)。

Analysis:

算法一:后缀数组
预处理前 i 个后缀能形成多少个不同的子串,之后二分,复杂度 $O(logn)$。
http://vjudge.net/problem/viewSource.action?id=1577464

算法二:后缀自动机
DP 出每个状态出发可以识别多少子串。之后在 SAM 上,逐个字符尝试。
。。。这种方法时间复杂度较差(依赖于子串长度)、想要通过此题需要常数优化和一定运气。。。
http://vjudge.net/problem/viewSource.action?id=2604504