作者a127a127 (TDYa127)
看板Prob_Solve
標題Re: [問題] LCS with O(nlogn)
時間Sun Nov 26 01:47:53 2006
※ 引述《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
1F：→ a127a127:想一想還是回來補充一下 弄成LIS會更快+好寫 04/05 22:38