某岛

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