#include <iostream>
#include <algorithm>

using namespace std;

int lcs(string x, string y)
{
    int m = x.length();
    int n = y.length();
    int curr[n+1], prev[n+1]; // take two array of shorter length to keep track of previous rows

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                curr[j] = 0;
            else {
                if (x[i-1] == y[j-1])
                    curr[j]= 1 + prev[j-1];
                else
                    curr[j] = max(prev[j], prev[j-1]);
            }
        }

        for (int start = 0; start <= n; start++)
            prev[start] = curr[start];
    }

    return curr[n];
}

int wrapperLCS(string x, string y) // to keep a check that always the shorter length string is passed as second parameter
{
    if (x.length() >= y.length())
        return lcs(x, y);
    else
        return lcs(y, x);
}

int main()
{
    string x = "human";
    string y = "chimpanzee";

    cout << "Length of Longest common Subsequence : " << wrapperLCS(x, y) << endl;

    return 0;
}