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