Preparation/LongestCommonSubsequence.cpp at master · yukty2000/Preparation · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
GFG Question
Given two sequences, find the length of longest subsequence present in both of them. Both the strings are of uppercase.

Input:
A = 6, B = 6
str1 = ABCDGH
str2 = AEDFHR
Output: 3

Input:
A = 3, B = 2
str1 = ABC
str2 = AC
Output: 2

*/

// function to find longest common subsequence

int lcs(int x, int y, string s1, string s2){

    int **Dp=(int **)malloc((x+1)*sizeof(int *));
    for(int i=0;i<=x;i++)
        Dp[i]=(int *)malloc((y+1)*sizeof(int));
    for(int i=0;i<=x;i++)
        Dp[i][0]=0;
    for(int i=0;i<=y;i++)
        Dp[0][i]=0;
    for(int i=1;i<=x;i++)
    {
        for(int j=1;j<=y;j++)
        {
            if(s1[i-1]==s2[j-1])
                Dp[i][j]=1+Dp[i-1][j-1];
            else
                Dp[i][j]=max(Dp[i-1][j],Dp[i][j-1]);
        }
    }
    int ans=Dp[x][y];
    for(int i=0;i<=x;i++)
        free(Dp[i]);
    free(Dp);
    return ans;
}