Dynamic_Programming/2.8)LCSubstring at main · Atharva-Morankar-09/Dynamic_Programming · 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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

GFG - https://practice.geeksforgeeks.org/problems/longest-common-substring1452/1

1) Recursion :

class Solution{
    public:

    int rec(string S1, string S2, int i, int j, int ans)
    {
        if(i==0 || j==0)
        {
            return 0;
        }

        if(S1[i-1]==S2[j-1])
        {
            ans=rec(S1,S2,i-1,j-1,ans+1);
        }
        else
        {
            return max(ans, max(rec(S1,S2,i-1,j,0), rec(S1,S2,i,j-1,0)));
        }
      return ans;
    }

    int longestCommonSubstr (string S1, string S2, int n, int m)
    {
        return rec(S1,S2,n,m,0);
    }
};

----------------------------------------------------------------------------------------------------------------------------------------------------------------------

2) Memoization :

class Solution{
    public:

    int rec(string S1, string S2, int i, int j, int ans, vector<vector<int>>& dp)
    {
        if(i==0 || j==0)
        {
            return ans;
        }

        if(dp[i-1][j-1]!=-1)
        {
            return dp[i-1][j-1];
        }

        if(S1[i-1]==S2[j-1])
        {
            ans=rec(S1,S2,i-1,j-1,ans+1,dp);
        }
        else
        {
            return max(ans, max(rec(S1,S2,i-1,j,0,dp), rec(S1,S2,i,j-1,0,dp)));
        }
      return dp[i][j]=ans;
    }

    int longestCommonSubstr (string S1, string S2, int n, int m)
    {
        vector<vector<int>> dp(n+1, vector<int>(m+1,-1));
        return rec(S1,S2,n,m,0,dp);
    }
};

------------------------------------------------------------------------------------------------------------------------------------------------------------------

3) Tabulation :

class Solution{
    public:

    int longestCommonSubstr (string S1, string S2, int n, int m)
    {
        int ans=0;
        vector<vector<int>> dp(n+1, vector<int> (m+1,0));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(S1[i-1]==S2[j-1])
                {
                    dp[i][j] = 1+dp[i-1][j-1];
                    ans=max(ans,dp[i][j]);
                }
                else
                {
                    dp[i][j]=0;
                }
            }
        }

      return ans;
    }
};