作者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