lcs

string getLongestCommonSubString(string a, string b)
{
    /* 
    dp[i, j] 为a[0, i - 1] 与 b[0, j - 1]末尾连续相等元素的数量

    dp[i, j] = 0                        (a[i] != b[j])
    dp[i, j] = dp[i - 1, j - 1] + 1     (a[i] == b[j])
    */
    vector<vector<int>> dp(a.length() + 1, vector<int>(b.length() + 1, 0));
    int index = 0;
    int maxLen = 0;
    for (int i = 1; i <= a.length(); i++) {
        for (int j = 1; j <= b.length(); j++) {
            if (a[i - 1] != b[j - 1]) {
                dp[i][j] = 0;
            } 
            else {
                dp[i][j] = dp[i - 1][j - 1] + 1;

                if (dp[i][j] > maxLen) {
                    maxLen = dp[i][j];
                    index = i - 1;
                }
            }
        }
    }

    return a.substr(index - maxLen + 1, maxLen);
}

void getLongestCommonSubStrigTest()
{
    string a = "cuiolf1234567cpomge12345678abcc";
    string b = "uzvldmf1234567vhhaocjl12345678accc";

    cout << a << endl;
    cout << b << endl;
    cout << "common: " << getLongestCommonSubString(a, b) << endl;
}

string getLongestCommonSubsequence(string a, string b)
{
    /*
    dp[i, j]表示a[0, i - 1]与b[0, j - 1]最长公共序列的长度

    dp[i, j] = 0                                (i == 0 || j == 0)
    dp[i, j] = dp[i -1, j - 1] + 1              a[i] == b[j]
    dp[i, j] = max(dp[i - 1, j] ,dp[i, j -1])   a[i] != b[j]
    */
    vector<vector<int>> dp(a.length() + 1, vector<int>(b.length() + 1));

    for (int i = 0; i <= a.length(); i++) {
        for (int j = 0; j <= b.length(); j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            }
            else {
                if (a[i - 1] == b[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
    }

    // show dp
    //for (vector<int> row : dp) {
    //    for (int i : row) {
    //        cout << i << " ";
    //    }

    //    cout << endl;
    //}

    // create LCS
    string lcs = "";
    int row = a.length();
    int col = b.length();
    int len = dp[row][col];
    while (len) {
        //cout << "(" << row << ", " << col << ")" << endl;
        if (a[row - 1] == b[col - 1]) {
            lcs.append(1, a[row - 1]);
            len--;
            row--;
            col--;
        }
        else {
            if (dp[row - 1][col] == len) {
                row--;
            }
            else {
                col--;
            }
        }
    }

    reverse(lcs.begin(), lcs.end());
    return lcs;
}

void getLongestCommonSubsequenceTest()
{
    string a = "c1z2xcc3te4bjt5htu6dfa";
    string b = "j1lg2jk3f4jk5ky6vcz";

    cout << a << endl;
    cout << b << endl;
    cout << "lcs: " << getLongestCommonSubsequence(a, b) << endl;
}