#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;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBsY3Moc3RyaW5nIHgsIHN0cmluZyB5KQp7CiAgICBpbnQgbSA9IHgubGVuZ3RoKCk7CiAgICBpbnQgbiA9IHkubGVuZ3RoKCk7CiAgICBpbnQgY3VycltuKzFdLCBwcmV2W24rMV07IC8vIHRha2UgdHdvIGFycmF5IG9mIHNob3J0ZXIgbGVuZ3RoIHRvIGtlZXAgdHJhY2sgb2YgcHJldmlvdXMgcm93cwoKICAgIGZvciAoaW50IGkgPSAwOyBpIDw9IG07IGkrKykgewogICAgICAgIGZvciAoaW50IGogPSAwOyBqIDw9IG47IGorKykgewogICAgICAgICAgICBpZiAoaSA9PSAwIHx8IGogPT0gMCkKICAgICAgICAgICAgICAgIGN1cnJbal0gPSAwOwogICAgICAgICAgICBlbHNlIHsKICAgICAgICAgICAgICAgIGlmICh4W2ktMV0gPT0geVtqLTFdKQogICAgICAgICAgICAgICAgICAgIGN1cnJbal09IDEgKyBwcmV2W2otMV07CiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgY3VycltqXSA9IG1heChwcmV2W2pdLCBwcmV2W2otMV0pOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICBmb3IgKGludCBzdGFydCA9IDA7IHN0YXJ0IDw9IG47IHN0YXJ0KyspCiAgICAgICAgICAgIHByZXZbc3RhcnRdID0gY3VycltzdGFydF07CiAgICB9CgogICAgcmV0dXJuIGN1cnJbbl07Cn0KCmludCB3cmFwcGVyTENTKHN0cmluZyB4LCBzdHJpbmcgeSkgLy8gdG8ga2VlcCBhIGNoZWNrIHRoYXQgYWx3YXlzIHRoZSBzaG9ydGVyIGxlbmd0aCBzdHJpbmcgaXMgcGFzc2VkIGFzIHNlY29uZCBwYXJhbWV0ZXIKewogICAgaWYgKHgubGVuZ3RoKCkgPj0geS5sZW5ndGgoKSkKICAgICAgICByZXR1cm4gbGNzKHgsIHkpOwogICAgZWxzZQogICAgICAgIHJldHVybiBsY3MoeSwgeCk7Cn0KCmludCBtYWluKCkKewogICAgc3RyaW5nIHggPSAiaHVtYW4iOwogICAgc3RyaW5nIHkgPSAiY2hpbXBhbnplZSI7CgogICAgY291dCA8PCAiTGVuZ3RoIG9mIExvbmdlc3QgY29tbW9uIFN1YnNlcXVlbmNlIDogIiA8PCB3cmFwcGVyTENTKHgsIHkpIDw8IGVuZGw7CgogICAgcmV0dXJuIDA7Cn0K