QUESTION
Given 2 strings a and b of equal length, what’s the longest string(s) that can be constructed such that it is a child of both.\n\nA string x is said to be a child of a string y if x can be formed by deleting 0 or more characters from y. \n\nFor example, ABCD and ABDC has two children with maximum length 3, ABC and ABD. Note that we will not consider ABCD as a common child because C doesn’t occur before D in the second string.\n\nInput format\n\nTwo strings, a and b , with a newline separating them.\n\nConstraints\n\n1<= |a|,|b| <= 5000\n\nAll characters are upper cased and lie between ASCII values 65-90.\n\nOutput format\n\nPrint the length of the longest string s , such that s is a child of both a and b.
ANSWER
#include<iostream>
#include<cstring>
using namespace std;
int n,LCS[5010][5010];
char A[5010],B[5010];
int main()
{
cin>>(A+1);
cin>>(B+1);
n=strlen(A+1);
int i,j,gasit;
gasit=0;
for(i=n;i>0;i--)
{
if(gasit==1)
LCS[i][n]=1;
else
{
if(A[i]==B[n])
{
gasit=1;
LCS[i][n]=1;
}
else
LCS[i][n]=0;
}
}
gasit=0;
for(j=n;j>0;j--)
{
if(gasit==1)
LCS[n][j]=1;
else
{
if(A[n]==B[j])
{
gasit=1;
LCS[n][j]=1;
}
else
LCS[n][j]=0;
}
}
for(i=n-1;i>0;i--)
{
for(j=n-1;j>0;j--)
{
if(A[i]!=B[j])
LCS[i][j]=max(LCS[i+1][j],LCS[i][j+1]);
else
LCS[i][j]=max(1+LCS[i+1][j+1],max(LCS[i+1][j],LCS[i][j+1]));
}
}
cout<<LCS[1][1]<<"\n";
return 0;
}