#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
void lcs( char *X, char *Y, int m, int n )
{
int L[m+1][n+1];
/* Following steps build L[m+1][n+1] in bottom up fashion. Note
that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
for (int i=0; i<=m; i++)
{
for (int j=0; j<=n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i-1] == Y[j-1])
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}
// Following code is used to print LCS
int index = L[m][n];
// Create a character array to store the lcs string
char lcs[index+1];
lcs[index] = '\0'; // Set the terminating character
// Start from the right-most-bottom-most corner and
// one by one store characters in lcs[]
int i = m, j = n;
while (i > 0 && j > 0)
{
// If current character in X[] and Y are same, then
// current character is part of LCS
if (X[i-1] == Y[j-1])
{
lcs[index-1] = X[i-1]; // Put current character in result
i--; j--; index--; // reduce values of i, j and index
}
// If not same, then find the larger of two and
// go in the direction of larger value
else if (L[i-1][j] > L[i][j-1])
i--;
else
j--;
}
// Print the lcs
cout << "LCS of " << X << " and " << Y << " is " << lcs;
}
int main()
{
char X[] = "AASDGX";
char Y[] = "AAWD";
int m = strlen(X);
int n = strlen(Y);
lcs(X, Y, m, n);
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGNzdHJpbmc+CiNpbmNsdWRlPGNzdGRsaWI+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKLyogUmV0dXJucyBsZW5ndGggb2YgTENTIGZvciBYWzAuLm0tMV0sIFlbMC4ubi0xXSAqLwp2b2lkIGxjcyggY2hhciAqWCwgY2hhciAqWSwgaW50IG0sIGludCBuICkKewoJICAgaW50IExbbSsxXVtuKzFdOwogCiAgIAkvKiBGb2xsb3dpbmcgc3RlcHMgYnVpbGQgTFttKzFdW24rMV0gaW4gYm90dG9tIHVwIGZhc2hpb24uIE5vdGUKICAgICAgCXRoYXQgTFtpXVtqXSBjb250YWlucyBsZW5ndGggb2YgTENTIG9mIFhbMC4uaS0xXSBhbmQgWVswLi5qLTFdICovCiAgIAlmb3IgKGludCBpPTA7IGk8PW07IGkrKykKICAgCXsKICAgICAJZm9yIChpbnQgaj0wOyBqPD1uOyBqKyspCiAgICAgCXsKICAgICAgIAkJaWYgKGkgPT0gMCB8fCBqID09IDApCgkgICAgICAgICAJTFtpXVtqXSA9IDA7CiAgICAgICAJCWVsc2UgaWYgKFhbaS0xXSA9PSBZW2otMV0pCiAgICAgICAgIAkJTFtpXVtqXSA9IExbaS0xXVtqLTFdICsgMTsKICAgICAgIAkJZWxzZQogICAgICAgICAJCUxbaV1bal0gPSBtYXgoTFtpLTFdW2pdLCBMW2ldW2otMV0pOwogICAgIAl9CiAgIAl9CiAKICAgCS8vIEZvbGxvd2luZyBjb2RlIGlzIHVzZWQgdG8gcHJpbnQgTENTCiAgIAlpbnQgaW5kZXggPSBMW21dW25dOwogCiAgIAkvLyBDcmVhdGUgYSBjaGFyYWN0ZXIgYXJyYXkgdG8gc3RvcmUgdGhlIGxjcyBzdHJpbmcKICAgCWNoYXIgbGNzW2luZGV4KzFdOwogICAJbGNzW2luZGV4XSA9ICdcMCc7IC8vIFNldCB0aGUgdGVybWluYXRpbmcgY2hhcmFjdGVyCiAKICAgCS8vIFN0YXJ0IGZyb20gdGhlIHJpZ2h0LW1vc3QtYm90dG9tLW1vc3QgY29ybmVyIGFuZAogICAJLy8gb25lIGJ5IG9uZSBzdG9yZSBjaGFyYWN0ZXJzIGluIGxjc1tdCiAgIAlpbnQgaSA9IG0sIGogPSBuOwogICAJd2hpbGUgKGkgPiAwICYmIGogPiAwKQogICAJewogICAgICAJLy8gSWYgY3VycmVudCBjaGFyYWN0ZXIgaW4gWFtdIGFuZCBZIGFyZSBzYW1lLCB0aGVuCiAgICAgIAkvLyBjdXJyZW50IGNoYXJhY3RlciBpcyBwYXJ0IG9mIExDUwogICAgICAJaWYgKFhbaS0xXSA9PSBZW2otMV0pCiAgICAgIAl7CiAgICAgICAgICAJbGNzW2luZGV4LTFdID0gWFtpLTFdOyAvLyBQdXQgY3VycmVudCBjaGFyYWN0ZXIgaW4gcmVzdWx0CiAgICAgICAgICAJaS0tOyBqLS07IGluZGV4LS07ICAgICAvLyByZWR1Y2UgdmFsdWVzIG9mIGksIGogYW5kIGluZGV4CiAgICAgIAl9CiAKICAgICAgCS8vIElmIG5vdCBzYW1lLCB0aGVuIGZpbmQgdGhlIGxhcmdlciBvZiB0d28gYW5kCiAgICAgIAkvLyBnbyBpbiB0aGUgZGlyZWN0aW9uIG9mIGxhcmdlciB2YWx1ZQogICAgICAJZWxzZSBpZiAoTFtpLTFdW2pdID4gTFtpXVtqLTFdKQogICAgICAgICAJaS0tOwogICAgICAJZWxzZQogICAgICAgICAJai0tOwogICAJfQogCiAgIAkvLyBQcmludCB0aGUgbGNzCiAgIAljb3V0IDw8ICJMQ1Mgb2YgIiA8PCBYIDw8ICIgYW5kICIgPDwgWSA8PCAiIGlzICIgPDwgbGNzOwp9CiAKaW50IG1haW4oKQp7CiAgCWNoYXIgWFtdID0gIkFBU0RHWCI7CiAgCWNoYXIgWVtdID0gIkFBV0QiOwogIAkKICAJaW50IG0gPSBzdHJsZW4oWCk7CiAgCWludCBuID0gc3RybGVuKFkpOwogIAkKICAJbGNzKFgsIFksIG0sIG4pOwogIAkKICAJcmV0dXJuIDA7Cn0=