字符串应用之最长公共子序列和最长公共子串

迷南。 2022-07-12 00:25 203阅读 0赞

## 最长公共子序列 ##

Xm表示X串的前m个字符，即x0,x1...xm−1  
LCS(Xm,Yn)即X的前m个字符和Y的前n个字符的最长公共子序列。

动规方程如下：

LCS(Xm,Yn)=\{ LCS(Xm−1,Yn−1)\+Xmmax(LCS(Xm−1,Yn),LCS(Xm,Yn−1)),xm=xn,xm≠yn

//最长公共子序列
    int longestCommonSubsequence(string A, string B) {
        int m = A.size();
        int n = B.size();
        vector<vector<int>>dp(m + 1, vector<int>(n + 1));
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (A[i] == B[j])
                {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                }
                else
                {
                    dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
    
                }
            }
        }
    
        int i = m - 1;
        int j = n - 1;
        string s;
        //记录最长子序列并打印
        while (i != -1 && j != -1)
        {
            if (A[i] == B[j])
            {
                s += A[i];
                --i;
                --j;
            }
            else
            {
                if ( (dp[i+1][j ] > dp[i ][j+1]))
                {
                    --j;
                }
                else
                {
                    --i;
                }
            }
        }
    
        string res(s.rbegin(), s.rend());
        cout << res << endl;
        return dp[m][n];
        // write your code here
    }

## 最长公共子串 ##

最长公共子串，由于匹配的字串必须在A、B串都是连续的，因此在更新dp\[i\]\[j\]的时候只能从dp\[i-1\]\[j-1\]。

//最长公共字串
    int longestCommonSubstring(string &A, string &B) {
        // write your code here
        size_t m = A.size();
        size_t n = B.size();
        int res = 0;
        vector<vector<int>> dp(m, vector<int>(n));
    
        for (int i = 0; i < static_cast<int>(m); ++i)
        {
            for (int j = 0; j < static_cast<int>(n); ++j)
            {
                if (A[i] == B[j])
                {
                    if (i>0 && j>0)
                    {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    }
                    else
                    {
                        dp[i][j] = 1;
                    }
                }
                if (res < dp[i][j])
                {
                    res = dp[i][j];
                }
            }
        }
        return res;
    }