最長公共子序列（LCSubstring）和最長公共子串（LCSunsequence）問題

最長公共子序列（Longest Common Subsequence）與最長公共子串（Longest Common Substring）的差別： 子序列問題隻需保持字元相對順序一緻，并不要求連續，而子串問題要求字元在原字元串中是連續的。

一、最長公共子序列（Longest Common Subsequence）（動态規劃)

根據下列公式來編寫程式：

程式步驟如下：

1、構造dp數組（二維數組多出一行一列來儲存dp初始狀态的0值）；

2、正序構造dp數組：根據公式給dp數組指派（注意下标值(

str1[i-1]

與

str2[j-1]

）與

dp[i][j]

對應)）；

3、結果輸出：倒序周遊dp數組，如果

目前位置

的

str1[i-1]==str2[j-1]

， 則将該點對應的值插入的結果字元串的頭部并且

i--; j--;

，如果

目前位置

的

dp值

與

上方

或

左方

的

dp值

相同，則向上或向左移動。如此循環，直到

i < 0 || j < 0

。 （因為最長公共子序列不一定唯一，這樣隻是輸出一種方案，所有的LCS輸出見

PrintAllLCS()

）。

4、輸出LCSubsequence；

#include <iostream>
#include <string>
#include <vector>
#include <set>
using namespace std;
set<string> allRes;

int Max(int a, int b) {
    return a > b ? a : b;
}

void PrintAllLCSubsequence(string &str1, string &str2, int i, int j,
                 vector<vector<int>> &dpvec, string res) {
    //print all LCS
    if (i == 0 || j == 0) {
        if (allRes.find(res) == allRes.end()) {
            cout << res << endl;
            allRes.insert(res);
        }
        return ;
    }
    if (i > 0 && j > 0) {
        if (str1[i-1] == str2[j-1]) {
            string tmp = str1[i-1] + res;
            PrintAllLCSubsequence(str1, str2, i-1, j-1, dpvec, tmp);
        } else {
            if (dpvec[i][j] == dpvec[i-1][j])
                PrintAllLCSubsequence(str1, str2, i-1, j, dpvec, res);

            if (dpvec[i][j] == dpvec[i][j-1])
                PrintAllLCSubsequence(str1, str2, i, j-1, dpvec, res);
        }
    }
}

void PrintOneLCSubsequence(string &str1, string &str2, vector<vector<int>> &dpvec) {
    //print one LCS
    string res = "";
    int i = str1.size();
    int j = str2.size();

    while (i > 0 && j > 0) {
        if (str1[i-1] == str2[j-1]) {
            res = str1[i-1] + res;
            i--;
            j--;
        } else {
            if (dpvec[i][j] == dpvec[i-1][j])
                i--;
            else if (dpvec[i][j] == dpvec[i][j-1])
                j--;
        }
    }
    cout << res << endl;
}

int LCSubsequence(string &str1, string &str2) {
    int len1 = str1.size();
    int len2 = str2.size();
    if (len1 == 0 || len2 == 0)
        return 0;

    vector<vector<int>> dp(len1+1, vector<int>(len2+1));
    for (int i = 0; i <= len1; i++) {
        for (int j = 0; j <=len2; j++) {
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else if (str1[i-1] == str2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = Max(dp[i-1][j], dp[i][j-1]);
        }
    }
    PrintOneLCSubsequence(str1, str2, dp);
    //PrintAllLCSubsequence(str1, str2, len1, len2, dp, "");
    return dp[len1][len2];
}


           

二、最長公共子串（Longest Common Substring）（動态規劃）

這裡的最大公共字串要求的字串是連續的。

求字串的方法和求子序列方法類似：

當

str1[i] == str2[j]

時，子序列長度

dp[i][j] = dp[i - 1][j - 1] + 1

；隻是當

str1[i] != str2[j]

時，

dp[i][j] = 0

，而不是

max{dp[i-1][j], dp[i][j-1]}

。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

void PrintOneLCSubstring(string &str1, string &str2, vector<vector<int>> &dpvec, int maxLen) {
     //print LCS
    if (maxLen != 0) {
        for (int i = str1.size(); i > 0; i--) {
            for (int j = str2.size(); j > 0; j--) {
                if (dpvec[i][j] == maxLen) {
                    string res = "";
                    int a = i;
                    int b = j;
                    while (a > 0 && b > 0) {
                        res = str1[a-1] + res;
                        --a;
                        --b;
                    }
                    cout << res << endl;
                    return ;
                }
            }
        }
    }

    return ;

}
int LCSubstring(string &str1, string &str2) {
    int len1 = str1.size();
    int len2 = str2.size();
    if (len1 == 0 || len2 == 0)
        return 0;
    int maxLen = 0;
    vector<vector<int>> dp(len1+1, vector<int>(len2+1));
    for (int i = 0; i <= len1; i++) {
        for (int j = 0; j <=len2; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (str1[i-1] == str2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                if (dp[i][j] > maxLen)
                    maxLen = dp[i][j];
            } else
                dp[i][j] = 0;
        }
    }
    PrintOneLCSubstring(str1, str2, dp, maxLen);
    return maxLen;
}

int main() {
	string X = "asdfas";
	string Y = "werasdfaswer";
	cout << "The length of LCS is " << LCSubstring(X, Y);
	cout << endl;
	return 0;
}