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;
}