#include <bits/stdc++.h>
using namespace std;
// Function to find Longest common substring of sequences X[0..m-1] and Y[0..n-1]
string LCS(string X, string Y, int m, int n)
{
int maxlen = 0; // max length of Longest common substring
int endingIndex = m; // ending index of Longest common substring in X
// lookup[i][j] stores the length of LCS of substring X[0..i-1], Y[0..j-1]
int lookup[m + 1][n + 1];
// initialize all cells of lookup table to 0
memset(lookup, 0, sizeof(lookup));
// fill the lookup table in bottom-up manner
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
// if current character of X and Y matches
if (X[i - 1] == Y[j - 1])
{
lookup[i][j] = lookup[i - 1][j - 1] + 1;
// update the maximum length and ending index
if (lookup[i][j] > maxlen)
{
maxlen = lookup[i][j];
endingIndex = i;
}
}
}
}
// return Longest common substring having length maxlen
return X.substr(endingIndex - maxlen, maxlen);
}
// main function
int main()
{
string X = "DABCD", Y = "BABCA";
int m = X.length(), n = Y.length();
// Find Longest common substring
cout << "The Longest common substring is " << LCS(X, Y, m, n);
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovLyBGdW5jdGlvbiB0byBmaW5kIExvbmdlc3QgY29tbW9uIHN1YnN0cmluZyBvZiBzZXF1ZW5jZXMgWFswLi5tLTFdIGFuZCBZWzAuLm4tMV0Kc3RyaW5nIExDUyhzdHJpbmcgWCwgc3RyaW5nIFksIGludCBtLCBpbnQgbikKewoJaW50IG1heGxlbiA9IDA7CQkJLy8gbWF4IGxlbmd0aCBvZiBMb25nZXN0IGNvbW1vbiBzdWJzdHJpbmcKCWludCBlbmRpbmdJbmRleCA9IG07CS8vIGVuZGluZyBpbmRleCBvZiBMb25nZXN0IGNvbW1vbiBzdWJzdHJpbmcgaW4gWAoJCgkvLyBsb29rdXBbaV1bal0gc3RvcmVzIHRoZSBsZW5ndGggb2YgTENTIG9mIHN1YnN0cmluZyBYWzAuLmktMV0sIFlbMC4uai0xXQoJaW50IGxvb2t1cFttICsgMV1bbiArIDFdOwoKCS8vIGluaXRpYWxpemUgYWxsIGNlbGxzIG9mIGxvb2t1cCB0YWJsZSB0byAwCgltZW1zZXQobG9va3VwLCAwLCBzaXplb2YobG9va3VwKSk7CgoJLy8gZmlsbCB0aGUgbG9va3VwIHRhYmxlIGluIGJvdHRvbS11cCBtYW5uZXIKCWZvciAoaW50IGkgPSAxOyBpIDw9IG07IGkrKykKCXsKCQlmb3IgKGludCBqID0gMTsgaiA8PSBuOyBqKyspCgkJewoJCQkvLyBpZiBjdXJyZW50IGNoYXJhY3RlciBvZiBYIGFuZCBZIG1hdGNoZXMKCQkJaWYgKFhbaSAtIDFdID09IFlbaiAtIDFdKQoJCQl7CgkJCQlsb29rdXBbaV1bal0gPSBsb29rdXBbaSAtIDFdW2ogLSAxXSArIDE7CgkJCQkKCQkJCS8vIHVwZGF0ZSB0aGUgbWF4aW11bSBsZW5ndGggYW5kIGVuZGluZyBpbmRleAoJCQkJaWYgKGxvb2t1cFtpXVtqXSA+IG1heGxlbikKCQkJCXsKCQkJCQltYXhsZW4gPSBsb29rdXBbaV1bal07CgkJCQkJZW5kaW5nSW5kZXggPSBpOwoJCQkJfQoJCQl9CgkJfQoJfQoJCgkvLyByZXR1cm4gTG9uZ2VzdCBjb21tb24gc3Vic3RyaW5nIGhhdmluZyBsZW5ndGggbWF4bGVuIAoJcmV0dXJuIFguc3Vic3RyKGVuZGluZ0luZGV4IC0gbWF4bGVuLCBtYXhsZW4pOwp9CgovLyBtYWluIGZ1bmN0aW9uCmludCBtYWluKCkKewoJc3RyaW5nIFggPSAiREFCQ0QiLCBZID0gIkJBQkNBIjsKCWludCBtID0gWC5sZW5ndGgoKSwgbiA9IFkubGVuZ3RoKCk7CgoJLy8gRmluZCBMb25nZXN0IGNvbW1vbiBzdWJzdHJpbmcKCWNvdXQgPDwgIlRoZSBMb25nZXN0IGNvbW1vbiBzdWJzdHJpbmcgaXMgIiA8PCBMQ1MoWCwgWSwgbSwgbik7CgoJcmV0dXJuIDA7Cn0K