学步园

这个问题也是算法导论上提过的问题。注意这个问题是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]。

所以我们可以把这个问题的递归式写成：

下面就是一个C++的实现：

// Longest_Common_subsequence.cpp : Defines the entry point for the console application.<br /> //<br /> #include "stdafx.h"<br /> #include <vector><br /> #include <string><br /> #include <iostream><br /> #include "windows.h"<br /> /**<br /> * Description: Calulate the longest common subsequence<br /> *@param s1, first sequence<br /> *@param s2, second sequence<br /> *@param s3, result subsequence<br /> */<br /> template <typename T> void longest_common_subsequence(const T& s1, const T& s2, T& s3)<br /> {<br /> const size_t len1 = s1.size();<br /> const size_t len2 = s2.size();<br /> std::vector< std::vector<unsigned int> > d(len1 + 1, std::vector<unsigned int>(len2 + 1));<br /> std::vector< std::vector<unsigned int> > b(len1 + 1, std::vector<unsigned int>(len2 + 1));<br /> const int w = 1;<br /> const int n = 2;<br /> const int nw = 3;<br /> for(int i = 1; i <= len1; ++i)<br /> {<br /> for(int j = 1; j <= len2; ++j)<br /> {<br /> if (s1[i-1] == s2[j-1])<br /> {<br /> d[i][j] = d[i-1][j-1]+1;<br /> b[i][j] = nw;<br /> }<br /> else<br /> {<br /> if (d[i-1][j] >= d[i][j-1])<br /> {<br /> d[i][j] = d[i-1][j];<br /> b[i][j] = n;<br /> }<br /> else<br /> {<br /> d[i][j] = d[i][j-1];<br /> b[i][j] = w;<br /> }<br /> }<br /> }<br /> }<br /> s3.resize(d[len1][len2]);<br /> int i=len1;<br /> int j=len2;<br /> int k=d[len1][len2]-1;<br /> while ( k>=0 && i>0 && j>0 )<br /> {<br /> if ( b[i][j] == nw )<br /> {<br /> s3[k--] = s1[i-1];<br /> i -- ;<br /> j -- ;<br /> }<br /> else if (b[i][j] == n)<br /> i -- ;<br /> else if (b[i][j] == w)<br /> j --;<br /> else<br /> break;<br /> }<br /> }<br /> int _tmain(int argc, _TCHAR* argv[])<br /> {<br /> std::string s1("ABCBDAB");<br /> std::string s2("BDCABA");<br /> std::string s3;<br /> longest_common_subsequence(s1, s2, s3);<br /> std::cout<< s3 <<std::endl;<br /> system("pause");<br /> return 0;<br /> }<br />

在代码里面的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.<br /> //<br /> #include "stdafx.h"<br /> #include <vector><br /> #include <iostream><br /> #include <algorithm><br /> #include "windows.h"<br /> template <class T> unsigned int edit_distance(const T& s1, const T& s2)<br /> {<br /> const size_t len1 = s1.size(), len2 = s2.size();<br /> std::vector<std::vector<unsigned int> > d(len1 + 1, std::vector<unsigned int>(len2 + 1));<br /> for(int i = 1; i <= len1; ++i) d[i][0] = i;<br /> for(int i = 1; i <= len2; ++i) d[0][i] = i;<br /> for(int i = 1; i <= len1; ++i)<br /> for(int j = 1; j <= len2; ++j)<br /> 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) );<br /> return d[len1][len2];<br /> }</p> <p>int _tmain(int argc, _TCHAR* argv[])<br /> {<br /> std::string s1("ABCBDAB");<br /> std::string s2("BDCABA");<br /> std::cout << "edit distance = " << edit_distance(s1, s2) << std::endl;;<br /> system("pause");<br /> return 0;<br /> }<br />

想来这大概也是《编程之美》中提到的非递归的办法吧。时间复杂度和空间复杂度都是O(mn)。需要额外说明的一点是，尽管这两个问题比较类似，但是好像还不能直接简单的由一个问题推导出另一个问题。我原来有想法希望这两个问题可以互相推导是不正确的。