作者DJWS (...)
看板Prob_Solve
标题Re: [问题] LCS with O(nlogn)
时间Sat Nov 25 11:21:55 2006
※ 引述《seanwu (Blindest)》之铭言：
: 我用DP做LCS，应该是 O(n^2)
: 但写ACM的时候TLE了
: 看提示是说有 O(nlogn)的作法
: 请问要怎麽做呢?
目前尚未听说有人能在 O(nlogn) 解出 LCS 问题的 :P
ACM讨论板关於10949的讨论串
有人有贴出一篇论文的连结
H. Goeman, M Clausen,
A New Practical Linear Space Algorithm for the LCS Problem
这篇论文提到了一个解决 LCS 的好方法
所需的时间复杂度是 O(ns + min{mp, mlogm + p(n-p)})
应该是够快了!
－
抱歉..我不会缩网址
所以只好请你自己去ACM讨论板找link了 :D
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.90.80
※ 编辑: DJWS 来自: 140.112.90.80 (11/25 11:33)
1F：推 seanwu:多谢 :) 11/25 12:38
2F：推 dumpweed:google url shortener 07/04 22:58