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