算法实战3：最长公共子序列_最长公共子串实际的应用

作者：繁依Fanyi0 | 2024-02-15 22:06:45

踩

最长公共子串实际的应用

在很多实际应用中，经常需要比较两个序列的相似性，例如DNA，或者文档的查重，但是往往这些序列相同部分不一定是相连，中间可能存在一些干扰元素，这就需要找出这种最长的公共子序列。

序列：X=<A,B,C,B,D,A,B> Y=<B,D,C,A,B,A>

这两个序列最长的公共子序列（Longest Common Subsequence）是Z=<B,C,A,B> Z=<B,D,A,B>

如何用程序找出来呢？

-----------------

这道题是一个很经典的动态规划的题目，所以大家得好好掌握动态规划其中的奥秘。

通常，动态规划的解题思路是希望能够找到大问题的子问题，通过求解子问题的最优解，然后再合并找出大问题的最优解。

往往这种子问题的划分需要从后开始，就是从问题解决开始逆推。

假设我们这里找到了X和Y 的一个LCS，那么这里的LCS是否包括来X和Y的最后一个字符呢？

所以分类分成两类

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/87438

算法实战3：最长公共子序列_最长公共子串 实际的应用