Re: [問題] LCS with O(nlogn)
看板Prob_Solve (計算數學 Problem Solving)作者a127a127 (TDYa127)時間18年前 (2006/11/26 01:11)推噓0(0推 0噓 1→)留言1則, 1人參與討論串3/3 (看更多)
※ 引述《seanwu (Blindest)》之銘言：
: 我用DP做LCS，應該是 O(n^2)
: 但寫ACM的時候TLE了
: 看提示是說有 O(nlogn)的作法
: 請問要怎麼做呢?
如果是一個字只出現一次的LCS的確是可以做到O(nlogn)
假設兩個字串，一個a字串長度為m，一個b字串長度為n，n<=m
先用一個大小為n的陣列紀錄b對應的a的位置
假設那個陣列是pair[]
答案紀錄在ans[]裡面
對每一個ans[i]要去找一個最大的ans[x]+1 {x<i,pair(x)<pair(i)}
這可以用BST(平衡的話lg n)或是segment tree(lg m)做到 (樹的鍵值用pair(x))
總共有n個字要做，每個字要lg n的時間
所以總時間是O(nlogn)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.81.154.22
→
04/05 22:38, , 1F
04/05 22:38, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
