#include <bits/stdc++.h>
using namespace std;
// define maximum length of sequence X and Y
#define M 20
#define N 20
// create a 2D-array to store solutions of subproblems
// All its values will be initailzed by 0 by default
int lookup[M + 1][N + 1];
// Function to find length of Longest Common Subsequence of substring
// X[0..m-1] and Y[0..n-1]
int LCSLength(string X, string Y, int m, int n)
{
// return if we have reached the end of either string
if (m == 0 || n == 0)
return 0;
// if sub-problem is seen for the first time, solve it and
// store its result in a array
if (lookup[m][n] == 0)
{
// if last character of X and Y matches
if (X[m - 1] == Y[n - 1])
lookup[m][n] = LCSLength(X, Y, m - 1, n - 1) + 1;
else
// else if last character of X and Y don't match
lookup[m][n] = max(LCSLength(X, Y, m, n - 1), LCSLength(X, Y, m - 1, n));
}
// return the subproblem solution from the array
return lookup[m][n];
}
// main function
int main()
{
string X = "ABCBDAB", Y = "BDCABA";
cout << "The length of LCS is " << LCSLength(X, Y, X.length(), Y.length());
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovLyBkZWZpbmUgbWF4aW11bSBsZW5ndGggb2Ygc2VxdWVuY2UgWCBhbmQgWQojZGVmaW5lIE0gMjAKI2RlZmluZSBOIDIwCgovLyBjcmVhdGUgYSAyRC1hcnJheSB0byBzdG9yZSBzb2x1dGlvbnMgb2Ygc3VicHJvYmxlbXMKLy8gQWxsIGl0cyB2YWx1ZXMgd2lsbCBiZSBpbml0YWlsemVkIGJ5IDAgYnkgZGVmYXVsdCAKaW50IGxvb2t1cFtNICsgMV1bTiArIDFdOwoKLy8gRnVuY3Rpb24gdG8gZmluZCBsZW5ndGggb2YgTG9uZ2VzdCBDb21tb24gU3Vic2VxdWVuY2Ugb2Ygc3Vic3RyaW5nCi8vIFhbMC4ubS0xXSBhbmQgWVswLi5uLTFdCmludCBMQ1NMZW5ndGgoc3RyaW5nIFgsIHN0cmluZyBZLCBpbnQgbSwgaW50IG4pCnsKICAgIC8vIHJldHVybiBpZiB3ZSBoYXZlIHJlYWNoZWQgdGhlIGVuZCBvZiBlaXRoZXIgc3RyaW5nCiAgICBpZiAobSA9PSAwIHx8IG4gPT0gMCkKICAgICAgICByZXR1cm4gMDsKCiAgICAvLyBpZiBzdWItcHJvYmxlbSBpcyBzZWVuIGZvciB0aGUgZmlyc3QgdGltZSwgc29sdmUgaXQgYW5kIAogICAgLy8gc3RvcmUgaXRzIHJlc3VsdCBpbiBhIGFycmF5CiAgICBpZiAobG9va3VwW21dW25dID09IDApCiAgICB7CiAgICAgICAgLy8gaWYgbGFzdCBjaGFyYWN0ZXIgb2YgWCBhbmQgWSBtYXRjaGVzCiAgICAgICAgaWYgKFhbbSAtIDFdID09IFlbbiAtIDFdKQogICAgICAgICAgICBsb29rdXBbbV1bbl0gPSBMQ1NMZW5ndGgoWCwgWSwgbSAtIDEsIG4gLSAxKSArIDE7CiAgICAgICAgCiAgICAgICAgZWxzZQogICAgICAgIC8vIGVsc2UgaWYgbGFzdCBjaGFyYWN0ZXIgb2YgWCBhbmQgWSBkb24ndCBtYXRjaAogICAgICAgIGxvb2t1cFttXVtuXSA9IG1heChMQ1NMZW5ndGgoWCwgWSwgbSwgbiAtIDEpLCBMQ1NMZW5ndGgoWCwgWSwgbSAtIDEsIG4pKTsKICAgIH0KICAgIAogICAgLy8gcmV0dXJuIHRoZSBzdWJwcm9ibGVtIHNvbHV0aW9uIGZyb20gdGhlIGFycmF5CiAgICByZXR1cm4gbG9va3VwW21dW25dOwp9CgovLyBtYWluIGZ1bmN0aW9uCmludCBtYWluKCkKewogICAgc3RyaW5nIFggPSAiQUJDQkRBQiIsIFkgPSAiQkRDQUJBIjsKCiAgICBjb3V0IDw8ICJUaGUgbGVuZ3RoIG9mIExDUyBpcyAiIDw8IExDU0xlbmd0aChYLCBZLCBYLmxlbmd0aCgpLCBZLmxlbmd0aCgpKTsKCiAgICByZXR1cm4gMDsKfQo=