最长公共子序列Algo

Question

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

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

如果我们匹配字符串的第一个字符，那么algo仍然会产生最优搜索吗？例如

考虑输入字符串“AGGTAB”和“AXTXAYB”。第一个字符与字符串匹配。因此，LCS的长度可以写为：

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

LCS问题：最长公共子序列问题

Answer 1

是的，这也是一回事。

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

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

假设LCS从末尾开始减少，则右边的操作将从相反的一端进行，但结果是相同的。

这就是为什么您可以使用前缀的方式与它们在解释中处理后缀的方式相同:在过程中您将得到同样的递归缩减。

此外，如果你愿意的话，你可以做两端的裁减。然而，这将使算法变得非常复杂，而不会给您带来任何速度的回报。

Answer 2

那么，如果我们从最后开始执行LCS，那么您可以在用户提供的递归中直接使用长度变量(例如M，N)。另一方面，如果从开始索引中创建额外的变量，则必须创建额外的变量。这就是前一种方法被认为是标准的原因，否则就没有复杂性的差别，而且一切都是一样的。

LCS (M, N)
{
if(M==0 || N==0)
return 0;
elseif (a[M]!=b[N])
return max(LCS(M,N-1), LCS(M-1,N));
else
return 1 + LCS(M-1,N-1);
}

Answer 3

是的，你可以这样做，这不会改变时间的复杂性。从最后开始只是一个惯例的问题。