看板 [ Prob_Solve ]
討論串[問題] LCS with O(nlogn)
共 3 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] LCS with O(nlogn)
推噓0(0推 0噓 1→)留言1則，0人參與, 最新作者seanwu (Blindest)時間18年前 (2006/11/23 22:03), 編輯資訊
2
0
0
內容預覽:
我用DP做LCS，應該是 O(n^2). 但寫ACM的時候TLE了. 看提示是說有 O(nlogn)的作法. 請問要怎麼做呢?. --. ※ 發信站: 批踢踢實業坊(ptt.cc). ◆ From: 211.75.94.172.
#2
Re: [問題] LCS with O(nlogn)
推噓2(2推 0噓 0→)留言2則，0人參與, 最新作者DJWS (...)時間18年前 (2006/11/25 11:12), 編輯資訊
0
0
0
內容預覽:
目前尚未聽說有人能在 O(nlogn) 解出 LCS 問題的 :P. ACM討論板關於10949的討論串. 有人有貼出一篇論文的連結. H. Goeman, M Clausen,. A New Practical Linear Space Algorithm for the LCS Problem.
(還有76個字)
#3
Re: [問題] LCS with O(nlogn)
推噓0(0推 0噓 1→)留言1則，0人參與, 最新作者a127a127 (TDYa127)時間18年前 (2006/11/26 01:11), 編輯資訊
0
0
0
內容預覽:
如果是一個字只出現一次的LCS的確是可以做到O(nlogn). 假設兩個字串，一個a字串長度為m，一個b字串長度為n，n<=m. 先用一個大小為n的陣列紀錄b對應的a的位置. 假設那個陣列是pair[]. 答案紀錄在ans[]裡面. 對每一個ans[i]要去找一個最大的ans[x]+1 {x<i,p
(還有10個字)
首頁
上一頁
1
下一頁
尾頁