longestCommonSubsequence.cpp

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

using namespace std;

int longestCommonSubsequence(string s, string t) {
    vector<vector<int>> v(s.size() + 1, vector<int>(t.size() + 1, 0));
    for (int i = 0; i < s.size() + 1; ++i) {
        for (int j = 0; j < t.size() + 1; ++j) {
            int n = 0;
            if (i == 0 || j == 0) {
                n = 0;
            }
            else if (s[i - 1] == t[j -1]) {
                n = v[i - 1][j - 1] + 1;
            }
            else {
                n = max(v[i - 1][j], v[i][j - 1]);
            }
            v[i][j] = n;
        }
    }
    return v[s.size()][t.size()];
}


int main(int argc, char *argv[]) {
    string s = "abcde", t = "aobpc";
    cout << longestCommonSubsequence(s, t) << endl;
    
    return 0;
}