最长的公共子序列Algo

Question

在最长的公共子序列（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从端部减小，在右侧的操作将去从所述相对的端部，但是实现相同的结果。

这就是为什么你可以使用前缀的原因，就像他们在解释中使用后缀的方式一样：在这个过程中你会得到同样的递归减少。

此外，如果您愿意，您可以在两端进行折扣。然而，这会使算法复杂化，而不会给你任何加速的回报。

Answer 2

是的，你能做到这一点不会改变时间复杂度。从最后开始只是一个约定的问题。

Answer 3

那么事实证明，你可以直接使用长度变量（比如M，N）由用户提供的，如果我们从去年进行LCS递归的。另一方面，如果从start索引执行，则必须创建额外的变量。这就是以前的方法被认为是标准的原因，否则没有复杂性差异，一切都是一样的。

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); 
}