最长公共子序列和最长公共子串是两种很常见的用动态规划解题的算法。
区别在于：子序列不需要连续，子串需要连续。
先说一下怎样求最长公共子序列的长度以及其中一个最长子序列（如果有多个就随便输出一个）

    int longestCommonSubsequenceLength(string text1, string text2)
        {
        if(text1.size() == 0 || text2.size() == 0) return 0;
        vector<vector<int>> dp(text1.length() + 1, vector<int>(text2.length() + 1,0));
        for(int i = 1; i < text1.length() + 1; i++)
            {
          for(int j = 1; j < text2.length() + 1; j++)
                {
            if(text1[i-1] == text2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
          else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
      }
      return dp[text1.length()][text2.length()];
    }

   string lcs(string s1,string s2)
    {
        if(s1.size() == 0 || s2.size() == 0) return "";
        vector<vector<int>> dp(s1.size()+1, vector<int>(s2.size()+1,0));
        for(int i=1;i<=s1.size();i++)
        {
            for(int j=1;j<=s2.size();j++)
            {
                if(s1[i-1] == s2[j-1])
                {
                    dp[i][j] = dp[i-1][j-1] + 1;

                } else
                {
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
                
            }
        }
        string res = "";
        int i = s1.size();
        int j = s2.size();
        while (i>=1 && j>=1)
        {
            if(s1[i-1] == s2[j-1])
                {
                    res+=s1[i-1];
                    i--;
                    j--;
                } else if(dp[i-1][j] >= dp[i][j-1])
                {
                    i--;
                } else if(dp[i-1][j] < dp[i][j-1])
                {
                    j--;
                }
                
        }
        
        reverse(res.begin(),res.end());
        return res;
    }

再说怎么求最长公共子串的长度以及输出一个最长子串：

下图的代码res表示最长子串的长度，

s1.substr(maxEnd-maxLen,maxLen);//这个表示的是其中一个最长子串

    string longestCommonSubstrings(string s1,string s2)
    {
        if(s1.size() == 0 || s2.size() == 0) return "";
        vector<vector<int>> dp(s1.size()+1, vector<int>(s2.size()+1,0));
        int res = 0;
        int maxLen = 0;
        int maxEnd = 0;
        for(int i=1;i<=s1.size();i++)
        {
            for(int j=1;j<=s2.size();j++)
            {
                if(s1[i-1] == s2[j-1])
                {
                    dp[i][j] = dp[i-1][j-1]+1;
                } else
                {
                    dp[i][j] = 0;
                }
                res = max(res,dp[i][j]);

                if(dp[i][j] >= maxLen)
                {
                    maxLen = dp[i][j];
                    maxEnd = i;
                }
                
            }



        }

        /*
        cout<<"This dp two vector is "<<endl;
        for(int i=0;i<dp.size();i++)
        {
            for(int j=0;j<dp[i].size();j++)
            {
                cout<<dp[i][j]<<" ";
            }
            cout<<endl;
        }
                */
        cout<<"Final res is "<<res<<endl;
        
        

        //return res;

        return s1.substr(maxEnd-maxLen,maxLen);

    }

最长公共子序列和最长公共子串

全站热榜