[algo] timeline algorithm

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string shortestCommonSupersequence(string a, string b) {
        int m = a.size();
        int n = b.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0) continue;
                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]);
                }
            }
        }

        int i = m;
        int j = n;
        string res;

        while (i > 0 && j > 0) {
            if (a[i-1] == b[j-1]) {
                res += a[i-1];
                --i;
                --j;
            } else {
                if (dp[i-1][j] < dp[i][j-1]) {
                    res += b[--j];
                } else {
                    res += a[--i];
                }
            }
        }
        while (i > 0) res += a[--i];
        while (j > 0) res += b[--j];

        reverse(res.begin(), res.end());

        return res;
    }
    string shortestCommonSupersequencePlus(vector<string>& strs) {
        string res = strs[0];
        for (int i = 1; i < strs.size(); i++) {
            res = shortestCommonSupersequence(res, strs[i]);
        }
        return res;
    }
    string trans(string& a, string& pattern) {
        int i = 0;
        int j = 0;
        int m = a.size();
        int n = pattern.size();
        string res;
        while (i < m && j < n) {
            if (a[i] != pattern[j]) {
                res.push_back(' ');
                j++;
            } else {
                res.push_back(a[i]);
                i++;
                j++;
            }
        }
        return res;
    }
};


int main() {
    int n;
    vector<string> strs = {
        "ABCDEH",
        "ACDEFBH",
        "ADEHG"
    };
    Solution* sol = new Solution();
    string res = sol->shortestCommonSupersequencePlus(strs);
    cout << res << endl;
    cout << sol->trans(strs[0], res) << endl;
    cout << sol->trans(strs[1], res) << endl;
    cout << sol->trans(strs[2], res) << endl;

    return 0;
}

input:

ABCDEH
ACDEFBH
ADEHG
=========
output:

ABCDEFBHG
ABCDE  H
A CDEFBH
A  DE  HG