浦那
在最长公共子序列（LCS）问题中，为什么我们匹配字符串的最后一个字符。例如，请考虑输入字符串“AGGTAB”和“AXTXAYB”。最后一个字符与字符串匹配。因此，LCS的长度可以写成：
L(“AGGTAB”, “AXTXAYB”) = 1 + L(“AGGTA”, “AXTXAY”)
如果我们将字符串的第一个字符匹配，算法是否仍不会产生最佳搜索。例如
考虑输入字符串“AGGTAB”和“AXTXAYB”。首字符匹配字符串。因此，LCS的长度可以写成：
L(“AGGTAB”, “AXTXAYB”) = 1 + L(“GGTAB”, “XTXAYB”)
LCS问题：最长公共子序列问题
谢尔盖·卡里尼琴科（Sergey Kalinichenko）
是的，这是同一回事。
计算两个反向序列的LCS与反向之前反转两个序列的LCS相同。换一种说法，
REVERSE(LCS(A,B)) = LCS(REVERSE(A), REVERSE(B))
假设LCS从头开始减少，则右侧的操作将从另一头开始，但达到相同的结果。
这就是为什么您可以按与解释中的后缀相同的方式使用前缀的原因：在过程中您将获得相同的递归减少。
此外，如果需要，您可以减少两端的损耗。但是，这会使算法复杂得多，而不会给您带来任何加速的回报。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
我来说两句