[算法系列之十九]最长公共子序列

题目

最长公共子序列

分析

有两个字符串S1和S2，求一个最长公共子串，即求字符串S3，它们同时是S1和S2的子串，且要求它们的长度最长，并确定这个长度。这个问题我们称之为最长公共子序列问题。
与求最长递增子序列一样，我们首先将原问题分割成一些子问题，我们用dp[i][j]表示S1中前i个字符和S2中前j个字符分别组成的两个前缀字符串的最长公共子串长度。显然的，当i,j较小时我们可以直接给出答案，如dp[0][j] 必等于0。那么，假设我们已经求的dp[i][j](0 <= i < x,0 <= j < y)的所有值，考虑如何在这些值继而推的dp[x][y]，求的S1前x个字符组成的前缀子串和S2前y个字符组成的前缀子串的最长公共的子序列的长度。若S1[x] == S2[y],即S1中的第x个字符和S2中的第y个字符相同，同时由于他们都是各自前缀子串的最后一个字符，那么必存在一个最长的公共子串以S1[x]或S2[y]结尾。其他部分等价于S1中前x-1个字符和S2中前y-1个字符的最长公共子串。所以这个子串的长度比dp[x-1][y-1]增加1，即dp[x][y] = dp[x-1][y-1] + 1。相反的，若S1[x] != S2[y]，此时其最长的公共子串长度为S1中前x-1个字符和S2中前y个字符的最长公共子串的长度与S1中前x个字符和S2中前y-1个字符的最长公共子串的长度的较大者，即在两种情况下得到的最长公共子串都不会因为其中一个字符串又增加了一个字符长度发生改变。综上所述，dp[x][y] = max{dp[x][y-1] , dp[x-1][y]}。
总结一下,最长公共子序列问题的递推条件：
假设有两个字符串S1和S2，其中S1长度为n，S2长度为m,用dp[i][j]表示S1前i个字符组成的前缀子串与S2前j个字符组成的前缀子串的最长公共子串长度，那么：

dp[0][j] = 0 （0 <= j <= m） 
dp[i][0] = 0 （0 <= i <= n）
dp[i][j] = dp[i-1][j-1] + 1 （S1[i] == S2[j]）
dp[i][j] = max{dp[i][j-1],dp[i-1][j]} （S1[i] != S2[j]） 

代码

/*---------------------------------------------
*   日期：2015-02-12
*   作者：SJF0115
*   题目: 19.最长公共子序列
*   来源：算法系列
*   博客：
-----------------------------------------------*/
#include <iostream>
#include <algorithm>
using namespace std;


class Solution {
public:
    int LCS(string a,string b){
        int sizea = a.size();
        int sizeb = b.size();
        if(sizea <= 0 || sizeb <= 0){
            return 0;
        }//if
        int dp[sizea+1][sizeb+1];
        // 初始化
        for(int i = 0;i < sizea;++i){
            for(int j = 0;j < sizeb;++j){
                if(i == 0 || j == 0){
                    dp[i][j] = 0;
                }//if
            }//for
        }//for
        // 递推
        for(int i = 1;i <= sizea;++i){
            for(int j = 1;j <= sizeb;++j){
                if(a[i] == b[j]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }//else
                else{
                    dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
                }//else
            }//for
        }//for
        return dp[sizea][sizeb];
    }
};


int main() {
    Solution solution;
    string a("BDCABA");
    string b("ABCBDAB");
    cout<<solution.LCS(a,b)<<endl;
}

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>