问题描述
有什么方法可以找到O(NlogN)时间中两个序列的最长公共子序列吗?
Is there any way of finding the longest common subsequence of two sequences in O(NlogN) time?
我在某处读到有一种方法可以使用二进制搜索来实现.
I read somewhere that there is a way to achieve this using binary search.
我知道dp方法需要O(N )时间.
I know the dp approach that takes O(N) time.
推荐答案
在一般情况下,O(N ^ 2)动态编程算法是您可以做的最好的事情.但是,在某些特殊情况下,存在更好的算法.
For the general case, the O(N^2) dynamic programming algorithm is the best you can do. However, there exist better algorithms in some special cases.
- 字母大小有界
这是非常普遍的情况.由某些字母(例如英语)的字母组成的序列属于此类别.对于这种情况,可以使用四个俄罗斯人的方法.我不知道能搜索到什么.
This is a very common situation. Sequences consisting of letters from some alphabet (e.g. English) lie in this category. For this case, the O(N*M) algorithm can be optimised to get an O(N^2/logN) with method of four Russians. I don't know how exactly, you can search for it.
- 两个序列都包含不同的元素
一个示例问题是给出数字从1到N的两个排列,找到它们的LCS".可以用O(N * logN)求解.
假设序列为A和B.
定义一个序列C.C [i]是B [i]在A中的索引.(A [C [i]] = B [i])
A和B的LCS是C的最长的增长子序列.
An example problem is "Given two permutations of numbers from 1 to N, find their LCS". This one can be solved in O(N*logN).
Let the sequences be A and B.
Define a sequence C. C[i] is the index of B[i] in A. (A[C[i]] = B[i])
LCS of A and B is the longest increasing subsequence of C.
这篇关于在O(NlogN)时间中找到最长的公共子序列的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!