某岛

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

POJ 3261. Milk Patterns

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

Brief description:

。。求最长 k-重复子串。
。。也就是 max{lcp(l, r) | r-l = k}

Analysis:

非常经典的例题。

算法一：字符串哈希（70ms
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1563261

算法二：SA + LCP（40ms
http://vjudge.net/problem/viewSource.action?id=2604648

算法三：SA + 二分（40ms
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1563212

算法四：SA + 单调队列（30ms
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1563242

——————————

“看到这题 SAM 做不了直接傻眼了囧。。。 ” —— http://yc5-yc.blog.163.com/blog/static/137797109201441910522414/

算法五：SAM + MAP（400ms++

http://vjudge.net/problem/viewSource.action?id=2604642

（卧槽数据要不要这么弱。。（直接开 26 居然 秒 A 了。。。。
http://vjudge.net/problem/viewSource.action?id=2604640）

Posted by xiaodao
Category: 日常

« | »

  • Archives

    open all | close all