在O(NlogN)时间内找到最长的公共子序列

Question

有没有办法在O(NlogN)时间内找到两个序列中最长的公共子序列？

我在某处读到有一种方法可以使用二进制搜索来实现这一点.

我知道需要O(N ²)时间的dp方法.

Answer 1

对于一般情况,O(N ^ 2)动态编程算法是您可以做的最好的.但是,在某些特殊情况下存在更好的算法.

1. 字母大小有限

这是一种非常普遍的情况.由某些字母表中的字母组成的序列(例如英语)属于此类别.对于这种情况,可以优化O(N*M)算法以使用四个俄罗斯人的方法获得O(N ^ 2/logN).我不知道究竟是什么,你可以搜索它.

2. 两个序列都由不同的元素组成

一个示例问题是"给定从1到N的两个数字排列,找到它们的LCS".这个可以用O(N*logN)来解决.
令序列为A和B.
定义序列C.C [i]是A中B [i]的索引.(A [C [i]] = B [i])
A和B的LCS 最长增加 C的后续序列

Answer 2

动态规划方法，一般情况下为O(n ² ) 。对于某些其他情况，还有复杂度较低的算法：

• 对于固定的字母大小（不随n增长），有四个俄罗斯人的方法，可将时间缩短至O(n ² /log n)（请参阅此处）。

• 参见这里另一个进一步优化的案例。