#include <iostream>
#include <string>
using namespace std;
// Space optimized function to find length of Longest Common Subsequence
// of substring X[0..m-1] and Y[0..n-1]
int LCSLength(const string& X, const string& Y)
{
int m = X.length(), n = Y.length();
if (m == 0 || n == 0) {
return 0;
}
/// TODO: swap X and Y if m < n.
// allocate storage for one-dimensional array curr
int curr[n] = {0};
// fill the lookup table in bottom-up manner
for (int i = 0; i < m; i++)
{
//int prev2 = curr[-1], prev = curr[-1];
int prev2 = 0, prev = 0;
char ch = X[i];
for (int j = 0; j < n; j++)
{
int backup = curr[j], last;
// if current character of X and Y matches
if (ch == Y[j])
last = prev2 + 1;
// else if current character of X and Y don't match
else
last = max(backup, prev);
curr[j] = last;
prev2 = backup;
prev = last;
}
}
// LCS will be last entry in the lookup table
return curr[n - 1];
}
// main function
int main()
{
string X = "XMJYAUZ", Y = "MZJAWXU";
if (X.length() > Y.length())
cout << "The length of LCS is " << LCSLength(X, Y);
else
cout << "The length of LCS is " << LCSLength(Y, X);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy8gU3BhY2Ugb3B0aW1pemVkIGZ1bmN0aW9uIHRvIGZpbmQgbGVuZ3RoIG9mIExvbmdlc3QgQ29tbW9uIFN1YnNlcXVlbmNlCi8vIG9mIHN1YnN0cmluZyBYWzAuLm0tMV0gYW5kIFlbMC4ubi0xXQppbnQgTENTTGVuZ3RoKGNvbnN0IHN0cmluZyYgWCwgY29uc3Qgc3RyaW5nJiBZKQp7CglpbnQgbSA9IFgubGVuZ3RoKCksIG4gPSBZLmxlbmd0aCgpOwoJaWYgKG0gPT0gMCB8fCBuID09IDApIHsKCQlyZXR1cm4gMDsKCX0KCgkvLy8gVE9ETzogc3dhcCBYIGFuZCBZIGlmIG0gPCBuLgoKCS8vIGFsbG9jYXRlIHN0b3JhZ2UgZm9yIG9uZS1kaW1lbnNpb25hbCBhcnJheSBjdXJyCglpbnQgY3VycltuXSA9IHswfTsKCgkvLyBmaWxsIHRoZSBsb29rdXAgdGFibGUgaW4gYm90dG9tLXVwIG1hbm5lcgoJZm9yIChpbnQgaSA9IDA7IGkgPCBtOyBpKyspCgl7CgkgICAgLy9pbnQgcHJldjIgPSBjdXJyWy0xXSwgcHJldiA9IGN1cnJbLTFdOwoJICAgIGludCBwcmV2MiA9IDAsIHByZXYgPSAwOwoJICAgIGNoYXIgY2ggPSBYW2ldOwoJCWZvciAoaW50IGogPSAwOyBqIDwgbjsgaisrKQoJCXsKCQkgICAgaW50IGJhY2t1cCA9IGN1cnJbal0sIGxhc3Q7CgkJCS8vIGlmIGN1cnJlbnQgY2hhcmFjdGVyIG9mIFggYW5kIFkgbWF0Y2hlcwoJCQlpZiAoY2ggPT0gWVtqXSkKCQkJCWxhc3QgPSBwcmV2MiArIDE7CgoJCQkvLyBlbHNlIGlmIGN1cnJlbnQgY2hhcmFjdGVyIG9mIFggYW5kIFkgZG9uJ3QgbWF0Y2gKCQkJZWxzZQoJCQkJbGFzdCA9IG1heChiYWNrdXAsIHByZXYpOwoKCQkJY3VycltqXSA9IGxhc3Q7CgkJCXByZXYyID0gYmFja3VwOwoJCQlwcmV2ID0gbGFzdDsKCQl9Cgl9CgoJLy8gTENTIHdpbGwgYmUgbGFzdCBlbnRyeSBpbiB0aGUgbG9va3VwIHRhYmxlCglyZXR1cm4gY3VycltuIC0gMV07Cn0KCi8vIG1haW4gZnVuY3Rpb24KaW50IG1haW4oKQp7CglzdHJpbmcgWCA9ICJYTUpZQVVaIiwgWSA9ICJNWkpBV1hVIjsKCglpZiAoWC5sZW5ndGgoKSA+IFkubGVuZ3RoKCkpCgkJY291dCA8PCAiVGhlIGxlbmd0aCBvZiBMQ1MgaXMgIiA8PCBMQ1NMZW5ndGgoWCwgWSk7CgllbHNlCgkJY291dCA8PCAiVGhlIGxlbmd0aCBvZiBMQ1MgaXMgIiA8PCBMQ1NMZW5ndGgoWSwgWCk7CgoJcmV0dXJuIDA7Cn0=