Length of LCS

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;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro