Re: [問題] LCS with O(nlogn)
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間18年前 (2006/11/25 11:12)推噓2(2推 0噓 0→)留言2則, 2人參與討論串2/3 (看更多)
※ 引述《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)
推
11/25 12:38, , 1F
11/25 12:38, 1F
推
07/04 22:58, , 2F
07/04 22:58, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 3 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
