某岛

… : "…アッカリ～ン . .. . " .. .
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

Posted by xiaodao
Category: SPOJ
Tags:

« | »

  • Archives

    open all | close all