http://blog.csdn.net/hhygcy/article/details/3948969
这个问题也是算法导论上提过的问题。注意这个问题是Subsequence不是Substring。substring的话就是子串,子串的要求的连续相等的字符序列,而subsequence不要求连续。比如说ABCD和ABD。他们的longest common subsequence就是ABD。而Longest common substring就是AB。
这个问题和Edit Distance是同样的一类问题。解决这类的问题都是从一个优化的子结构开始得到递推式,从而给出一个一般的全局优化结构的过程。在这里,我们假定两个字符串分别是S1和S2。他们的长度是m和n。我们用M[i,j]来表示一个长度为i的S1和长度为j的S2的最优方案。我们要找的就是当M[m,n]是的方案。问题的关键就是要找到M[i,j]和之前的那些诸如M[1..i, 1..j]之间的关系。
我们把问题分成两种情况来讨论:
1. 如果S1[i] == S2[j]。就是i,j对应位置上的字符相等。那么可以得出M[i,j] = M[i-1,j-1]+1;为什么呢?可以想象的。如果M[i-1,j-1]也是一个最后方案,在这个最优方案上我们同时增加一个字符。而这两个字符又相等。那么我们只需要在这个M[i-1,j-1]的最优方案上++就可以了。
2. 如果S1[i] != S2[j]。那么就拿M[i-1,j]和M[i,j-1]来比较。M[i,j]的值就是M[i-1,j]和M[i,j-1]中大的值。这好比原来的字符串是S1[1...i-1]是ABC,S2[1...j-1]是ABE。那S1[1..i]是ABCE,S2[1..j]是ABEC。可以看出来这个时候M[i,j]不是由M[i-1,j-1]决定的,而是由ABCE和ABE或者ABC和ABEC来决定的,也就是M[i-1,j]和M[i,j-1]。
所以我们可以把这个问题的递归式写成:
在代码里面的d用来表示长度,也就是我们的M[i,j]数组,而b则用来回溯到这个S3。当然这里的流程也可以用这个图来说明:
这个问题是动态规划中非常基础的一个问题,这个问题其实和另一个前面提到的问题很类似。就是Edit Distance的问题。Edit Distance问题又被成为Levenshtein distance问题。这里的问题描述的就是两个字符串经过若干次修改(添加字符,删除字符,替换字符)变为两个完全相等字符串。这里的distance就是指最少的修改次数。其实这个也就是《编程之美》中的那个字符串相似度的问题。
相似的,我们还是定义一个M[i,j]的二维模型。这时候一样还是分析M[i,j]的递归式。这里的结果还是比较相近的。
如果S1[i] == S2[j]。那么M[i,j]就等于M[i-1,j-1],就是说在S1[i]==S2[j]的情况下M[i,j]不会发生变化,显然不需要做什么改动。
如果S1[i] != S2[j]的时候,那么就是M[i-1,j-1],M[i-1,j]和M[i,j-1]来做比较,我们取最小的那个值+1就可以了。这里的M[i-1,j-1],M[i-1,j]和M[i,j-1]对应了添加删除替换这些操作。M[i-1,j-1]可以替换最后一个S1[i]和S[j]来完成,而M[i-1,j]可以通过添加S1[i]来完成匹配。
这里我也把C++的代码贴出来参考一下:
- // Edit_Distance.cpp : Defines the entry point for the console application.
- //
- #include "stdafx.h"
- #include <vector>
- #include <iostream>
- #include <algorithm>
- #include "windows.h"
- template <class T> unsigned int edit_distance(const T& s1, const T& s2)
- {
- const size_t len1 = s1.size(), len2 = s2.size();
- std::vector<std::vector<unsigned int> > d(len1 + 1, std::vector<unsigned int>(len2 + 1));
- for(int i = 1; i <= len1; ++i) d[i][0] = i;
- for(int i = 1; i <= len2; ++i) d[0][i] = i;
- for(int i = 1; i <= len1; ++i)
- for(int j = 1; j <= len2; ++j)
- d[i][j] = std::min<> ( std::min<> (d[i - 1][j] + 1,d[i][j - 1] + 1), d[i - 1][j - 1] + (s1[i - 1] == s2[j - 1] ? 0 : 1) );
- return d[len1][len2];
- }
- int _tmain(int argc, _TCHAR* argv[])
- {
- std::string s1("ABCBDAB");
- std::string s2("BDCABA");
- std::cout << "edit distance = " << edit_distance(s1, s2) << std::endl;;
- system("pause");
- return 0;
- }
想来这大概也是《编程之美》中提到的非递归的办法吧。时间复杂度和空间复杂度都是O(mn)。需要额外说明的一点是,尽管这两个问题比较类似,但是好像还不能直接简单的由一个问题推导出另一个问题。我原来有想法希望这两个问题可以互相推导是不正确的。
相关推荐
### 最长公共子序列(Longest Common Subsequence, LCS) #### 定义与概念 最长公共子序列问题(LCS)是计算机科学中的一个经典问题,它涉及到在两个或多个序列中寻找最长的相同子序列。这里所说的“子序列”并不...
最长公共子序列(Longest Common Subsequence,LCS)是一个经典的计算机科学问题,涉及序列比较和算法设计。在本实验报告中,我们将深入探讨如何利用动态规划方法解决这一问题。 首先,LCS问题旨在找到两个给定序列...
最长公共子序列(Longest Common Subsequence,LCS)是一个经典的计算机科学问题,它涉及到序列比对和字符串处理。在两个或多个序列中,LCS是指没有改变原有顺序的情况下,存在于所有序列中的最长子序列。这个问题在...
实验报告的主题是“算法设计与分析”,关注的是使用动态规划解决最长公共子序列(Longest Common Subsequence, LCS)的问题。动态规划是一种有效的方法,它适用于具有最优子结构和子问题重叠性质的问题。在本实验中...
最长公共子序列(Longest Common Subsequence,简称LCS)问题属于计算机科学领域中的一个重要问题,尤其是在算法设计与分析方面。此问题的核心在于寻找两个序列的最长公共子序列。其中,“子序列”指的是在原序列中...
在讨论最长公共子序列(Longest Common Subsequence,简称LCS)问题时,通常会提及两种主要的算法实现方式:一种时间复杂度为O(n^2),另一种则通过优化达到O(nlogn)的时间复杂度。下面我们将详细介绍这两种算法。 *...
最长公共子序列(Longest Common Subsequence,简称LCS)是计算机科学中一个重要的算法问题,它主要应用于字符串比较、文本编辑、生物信息学等领域。在文本编辑器中,LCS用于比较两份文档的差异,帮助进行合并或冲突...
在深入解析给定代码之前,我们先来了解一下“最长公共子序列”(Longest Common Subsequence,简称LCS)的基本概念及其在计算机科学中的应用。LCS问题是一种典型的动态规划问题,广泛应用于生物信息学、文本编辑和...
最长公共子序列问题(Longest Common Subsequence,LCS)是计算机科学中一个经典的问题,它是指给定两个序列X和Y,找出它们的最长公共子序列。该问题具有重要的理论和实际意义,在很多领域都有应用,如数据压缩、...
最长公共子序列(Longest Common Subsequence,简称 LCS)是一个经典的计算机科学问题。它指的是在两个序列中找出最长的相同子序列。需要注意的是,这里的子序列并不一定是连续的。 ### 二、解决方法概述 本程序...
本篇文章将详细介绍如何使用C++语言解决最长公共子序列(Longest Common Subsequence, LCS)问题,并结合具体的代码示例进行深入剖析。文章将涵盖以下几个核心知识点: 1. **最长公共子序列问题介绍** 2. **动态...
最长公共子序列(Longest Common Subsequence,LCS)是计算机科学中一种经典的字符串问题,主要涉及算法设计和分析。它的目标是找到两个给定序列(通常为字符串)的最长子序列,该子序列在原序列中不需连续,但必须...
最长公共子序列(Longest Common Subsequence,LCS)问题是一个经典的计算机科学问题,主要涉及字符串处理和动态规划算法。在本场景中,我们使用C#编程语言来解决这个问题。C#是一种多范式编程语言,广泛应用于开发...
本次实验旨在使学生掌握如何运用动态规划策略来解决最长公共子序列(Longest Common Subsequence, LCS)问题,并通过编程实践加深对动态规划算法的理解。 #### 实验原理 **动态规划算法设计**是一种通过将复杂问题...
在计算机科学领域中,**最长公共子序列问题**(Longest Common Subsequence Problem, LCS)是一个经典的算法问题,它主要应用于文本比较、生物信息学中的DNA序列比对等领域。该问题的核心是找出两个序列的最长子序列...
最长公共子序列(Longest Common Subsequence,简称LCS)是计算机科学中一种经典的问题,主要应用于比较和分析两个或多个序列的相似性。在这个问题中,目标是找到两个序列的最长子序列,这个子序列不需要在原序列中...
最长公共子序列(Longest Common Subsequence,简称LCS)是计算机科学中一种经典的字符串问题,广泛应用于文本比较、生物信息学等领域。本实验报告主要围绕LCS算法的实现及其实验过程进行深入探讨。 首先,我们要...
最长公共子序列(Longest Common Subsequence, LCS)是计算机科学中的一个重要算法问题,主要应用于序列比较、文本处理和生物信息学等领域。本实验旨在帮助本科学生深入理解这一概念,并通过编写代码、分析流程和...
动态规划是一种强大的算法思想,广泛应用于计算机科学,特别是在解决最优化问题时,如寻找最长公共子序列(Longest Common Subsequence, LCS)。本主题聚焦于使用动态规划方法求解最长公共子序列问题,并通过C++语言...