最长公共子序列

Question

考虑两个序列X1..m和Y1..n。记忆算法将在O(m*n)时间内计算LCS。有没有更好的算法来找出LCS wrt时间？我猜对角的记忆化可以给我们O(min(m，n))的时间复杂度。

Answer 1

吉恩·迈尔斯在1986年提出了一个非常好的算法来解决这个问题，这里描述了：An O(ND) Difference Algorithm and Its Variations。

该算法所需的时间与序列之间的编辑距离成正比，因此当差异较小时，该算法的速度要快得多。它的工作原理是遍历所有可能的编辑距离，从0开始，直到找到可以构造编辑脚本(在某些情况下是LCS的对偶)的距离。这意味着，如果差额超过某个阈值，您可以“提前退出”，这有时很方便。

我相信这个算法仍然在许多diff实现中使用。

Answer 2

如果您事先知道您关心的最大大小k的上限，则可以通过在内部循环中添加额外的检查来强制LCS算法提前退出。这意味着当k << min(m，n)时，你可以得到很小的运行时间，尽管你正在做LCS。

Answer 3

是的，我们可以创建一个比O(m*n)阶更好的算法-即O(min(m，n))。找出一个长度..。只需比较每次递增时的对角线elements.and，假设它发生在c2,2中，然后将c2,2++和c2++,2中的所有值递增1。直到cm，m..(假设m