#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