test

main.cpp

#include <string.h>

#include <algorithm>
#include <cstring>
#include <iostream>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
int lcs_(const string &X, const string &Y);

int main() { cout << lcs_("abcde", "dce"); }

test.cpp

#include <string.h>

#include <algorithm>
#include <cstring>
#include <iostream>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;

struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;
    }
};

int lcs_(const string& X, const string& Y) {
    unordered_map<int, int> ht;
    unordered_map<pair<string, string>, int, hash_pair> indx;
    vector<pair<string, string>> items;
    unordered_map<int, vector<int>> edges;
    vector<int> args[2];

    int input = 0;
    int output = 1;

    auto p = make_pair(X, Y);
    items.emplace_back ( p);
    ht[0] = 0;
    indx[p] = 0;
    args[input].emplace_back(0);

    while (args[input].size() > 0) {
        for (auto node : args[input]) {
            auto x = items[node].first;
            auto y = items[node].second;
            if (x == "" || y == "")
                ;
            else {
                if (x[0] == y[0]) {
                    bool f = false;
                    auto p = make_pair(x.substr(1), y.substr(1));
                    if (indx[p] == 0) {
                        items.emplace_back(p);
                        indx[p] = items.size() - 1;
                        f = true;
                    }
                    int n = indx[p];
                    int level = ht[node];
                    ht[n] = level + 1;
                    if (f) args[output].emplace_back(n);

                    edges[node].emplace_back(n);

                }
                else {
                    bool f1 = false;
                    bool f2 = false;
                    auto p1 = make_pair(x.substr(1), y.substr(1));
                    auto p2 = make_pair(x.substr(1), y);
                    if (indx[p1] == 0) {
                        items.emplace_back(p1);
                        indx[p1] = items.size() - 1;
                        f1 = true;
                    }
                    if (indx[p2] == 0) {
                        items.emplace_back(p2);
                        indx[p2] = items.size() - 1;
                        f2 = true;
                    }

                    int n1 = indx[p1];
                    int n2 = indx[p2];
                    int level = ht[node];
                    ht[n1] = max(ht[n1], level + 1);
                    ht[n2] = max(ht[n2], level + 1);

                    if (f1) args[output].emplace_back(n1);
                    if (f2) args[output].emplace_back(n2);
                    edges[node].emplace_back(n1);
                    edges[node].emplace_back(n2);
                }
            }
        }
        args[input].clear();
        swap(input, output);
    }

    // now sort the
    vector<pair<int, int>> v;
    for (auto elem : ht) {
        v.emplace_back(elem);
    }
    sort(v.begin(), v.end(),
        [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.second > b.second;
        });

    for (auto i : v) cout << i.first << ' ' << i.second << '\n';
    cout << "items\n";
    for (auto i : items) cout << i.first << ' ' << i.second << '\n';
    cout << "edges\n";
    for (auto i : edges) {
        cout << i.first << ' ' << '\n';
        for (auto j : i.second) cout << '\t' << j << '\n';
    }
    cout << "indx\n";
    for (auto e : indx) {
        cout << e.first.first <<","<<e.first.second << " " << e.second <<"\n";
    }
    return 0;
}