longest common subsequence algorithm

1class Solution:
2    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
3        """
4        text1: horizontally
5        text2: vertically
6        """
7        dp = [[0 for _ in range(len(text1)+1)] for _ in range(len(text2)+1)]
8        
9        for row in range(1, len(text2)+1):
10            for col in range(1, len(text1)+1):
11                if text2[row-1]==text1[col-1]:
12                    dp[row][col] = 1+ dp[row-1][col-1]
13                else:
14                    dp[row][col] = max(dp[row-1][col], dp[row][col-1])
15        return dp[len(text2)][len(text1)]

1#include<bits/stdc++.h>
2using namespace std;
3
4const int MAX = 1001;
5
6int dp[MAX][MAX];
7bool visited[MAX][MAX];
8int x, y;
9string s1, s2;
10
11int lcs(int i, int j)
12{
13    if(i == x || j == y)
14        return 0;
15
16    if(visited[i][j])
17        return dp[i][j];
18
19    visited[i][j] = true;
20    int ans = 0;
21    if(s1[i] == s2[j])
22    {
23        ans = max(ans, 1+lcs(i+1, j+1));
24    }
25    else
26    {
27        ans = max(ans, lcs(i+1, j));
28        ans = max(ans, lcs(i, j+1));
29    }
30
31    dp[i][j] = ans;
32    return ans;
33}
34
35int main()
36{
37    cin >> x >> y;
38    cin >> s1 >> s2;
39
40    for(int i=0; i<=x; i++)
41    {
42        for(int j=0; j<=y; j++)
43        {
44            visited[i][j] = false;
45        }
46    }
47
48    cout << lcs(0, 0);
49    return 0;
50}
51

1int maxSubsequenceSubstring(char x[], char y[], 
2                            int n, int m) 
3{ 
4    int dp[MAX][MAX]; 
5  
6    // Initialize the dp[][] to 0. 
7    for (int i = 0; i <= m; i++) 
8        for (int j = 0; j <= n; j++) 
9            dp[i][j] = 0; 
10  
11    // Calculating value for each element. 
12    for (int i = 1; i <= m; i++) { 
13        for (int j = 1; j <= n; j++) { 
14  
15            // If alphabet of string X and Y are 
16            // equal make dp[i][j] = 1 + dp[i-1][j-1] 
17            if (x[j - 1] == y[i - 1]) 
18                dp[i][j] = 1 + dp[i - 1][j - 1]; 
19  
20            // Else copy the previous value in the 
21            // row i.e dp[i-1][j-1] 
22            else
23                dp[i][j] = dp[i][j - 1]; 
24        } 
25    } 
26  
27    // Finding the maximum length. 
28    int ans = 0; 
29    for (int i = 1; i <= m; i++) 
30        ans = max(ans, dp[i][n]); 
31  
32    return ans; 
33} 

1#include<iostream>
2using namespace std;
3int LCS(string s1,string s2,int n1,int n2)
4{
5    int dp[n1+1][n2+1],i,j;
6    for(i=0;i<n1+1;i++) dp[i][0]=0;
7    for(j=0;j<n2+1;j++) dp[0][j]=0;
8    for(i=1;i<n1+1;i++)
9    {
10        for(j=1;j<n2+1;j++)
11        {
12            if(s1[i-1]==s2[j-1])
13                dp[i][j]=1+dp[i-1][j-1];
14            else
15                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
16        }
17    }
18    return dp[n1][n2];
19}
20int main()
21{
22    string s1,s2;
23    int n1,n2;
24    cin>>s1>>s2;
25    n1 = s1.length();
26    n2 = s2.length();
27    cout<<LCS(s1,s2,n1,n2)<<endl;
28}
29