Given a rawTitle, and a list(or array) of clean titles. For each clean title,
the raw title can get a "match point". For example, if raw title is "senior software
engineer" and clean titles are "software engineer" and "mechanical engineer", the
"match point" will be 2 and 1. In this case we return "software engineer" because
it has higher "match point".

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>

using namespace std;
vector<string> split(string s) {
    vector<string> res;
    string tmp;
    for (int i = 0; i < s.size(); i++)
        if (s[i] == ' ') {
            res.push_back(tmp);
            tmp = "";
        }
        else tmp += s[i];
    if (tmp.size()) res.push_back(tmp);
    return res;
}
int calPoints(vector<string> rSplit, vector<string> cSplit) {
    vector<vector<int>> dp(rSplit.size(), vector<int>(cSplit.size()));
    //int res = 0;
    for (int i = 0; i < rSplit.size(); i++)
        for (int j = 0; j < cSplit.size(); j++) {
            if (i) dp[i][j] = dp[i - 1][j];
            if (j) dp[i][j] = max(dp[i][j], dp[i][j - 1]);
            if (rSplit[i] == cSplit[j]) {
                if (i == 0 || j == 0) dp[i][j] = 1;
                else dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
            }
        }
    return dp[rSplit.size() - 1][cSplit.size() - 1];
}

string normalizeTitle(string rT, vector<string> cT) {
    int maxPoint = 0;
    string res;
    vector<string> rSplit = split(rT);
    for (string s : cT) {
        int tmp = calPoints(rSplit, split(s));
        if (tmp > maxPoint) {
            maxPoint = tmp;
            res = s;
        }
        cout<<tmp<<' '<<s<<endl;
    }
    return res;
}

int main(int argc, char *argv[]) {
    vector<string> cleanTitles = {
        "2 1 3",
        "1 0 2 3 4",
        "0 1 2 3 4"};
    string rawTitle = "1 2 1 3 4";
    cout<<normalizeTitle(rawTitle, cleanTitles);
    return 0;
}