algorithm - 最长公共(public)子序列算法

Question

在最长公共(public)子序列 (LCS) 问题中，为什么我们要匹配字符串的最后一个字符。对于前 考虑输入字符串 “AGGTAB” 和 “AXTXAYB”。最后一个字符匹配字符串。所以LCS的长度可以写成:

L(“AGGTAB”, “AXTXAYB”) = 1 + L(“AGGTA”, “AXTXAY”)

如果我们匹配字符串的第一个字符，算法是否仍会产生最佳搜索。例如

考虑输入字符串 “AGGTAB” 和 “AXTXAYB”。第一个字符匹配字符串。所以LCS的长度可以写成:

L(“AGGTAB”, “AXTXAYB”) = 1 + L(“GGTAB”, “XTXAYB”)

LCS 问题:Longest Common Subsequence Problem

Answer 1

是的，这是一回事。

计算两个反转序列的 LCS 与反转两个序列在​​反转前的 LCS 相同。换句话说，

REVERSE(LCS(A,B)) = LCS(REVERSE(A), REVERSE(B))

假设LCS从末端开始减少，右边的操作将从另一端开始，但得到相同的结果。

这就是为什么您可以像处理解释中的后缀一样处理前缀:您将在此过程中获得相同类型的递归归约。

此外，如果您愿意，您可以在两端进行缩减。但是，这会使算法变得非常复杂，而不会给您带来任何加速返回。