algorithm - 在 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]是B[i]在A中的索引。(A[C[i]] = B[i])
A和B的LCS是最长的C的增加子序列。

Answer 2

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

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

• 请参阅此处的另一个进一步优化的案例。

Answer 3

假设指数时间假设（比 P 更严格，不等于 NP，但仍被广泛认为是正确的），对于任何正常数 eps，不可能在 O(N^{2 - eps}) 时间内完成，请参阅Karl Bringmann 和 Marvin Kunnemann 的“字符串问题和动态时间扭曲的二次条件下界”（arXiv 上的预印本可用）。

粗略地说，这意味着这个问题的一般情况不能比 O(N^2/log N) 更好地及时解决，所以如果你想要更快的算法，你必须考虑额外的约束（字符串的一些属性）或寻找近似解决方案。

Answer 4

两个序列之间最长的公共子序列本质上是 n 平方的。

Masek 和 Patterson (1980)使用所谓的“四个俄罗斯人”技术对 n-squared / log n 做了一个小的改进。

在大多数情况下，这种复杂的方法引入的额外复杂性并不能因为小幅收益而得到证明。出于实际目的，您可以将 n 平方方法视为典型应用中的合理最优值。

Answer 5

vector <int> LIS;
int LongestIncreasingSubsequence(int n){
    if(!n) return 0;
    LIS.emplace_back(arr[0]);
    for(int i = 1; i < n; i++){
        if(arr[i] > LIS.back()) LIS.emplace_back(arr[i]);
        else *lower_bound(LIS.begin(), LIS.end(), arr[i]) = arr[i];
    }
    return LIS.size();
}