Answers for "longest common subsequence"

longest common subsequence

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        """
        text1: horizontally
        text2: vertically
        """
        dp = [[0 for _ in range(len(text1)+1)] for _ in range(len(text2)+1)]
        
        for row in range(1, len(text2)+1):
            for col in range(1, len(text1)+1):
                if text2[row-1]==text1[col-1]:
                    dp[row][col] = 1+ dp[row-1][col-1]
                else:
                    dp[row][col] = max(dp[row-1][col], dp[row][col-1])
        return dp[len(text2)][len(text1)]

longest common subsequence codefroces

#include<bits/stdc++.h>
using namespace std;

const int MAX = 1001;

int dp[MAX][MAX];
bool visited[MAX][MAX];
int x, y;
string s1, s2;

int lcs(int i, int j)
{
    if(i == x || j == y)
        return 0;

    if(visited[i][j])
        return dp[i][j];

    visited[i][j] = true;
    int ans = 0;
    if(s1[i] == s2[j])
    {
        ans = max(ans, 1+lcs(i+1, j+1));
    }
    else
    {
        ans = max(ans, lcs(i+1, j));
        ans = max(ans, lcs(i, j+1));
    }

    dp[i][j] = ans;
    return ans;
}

int main()
{
    cin >> x >> y;
    cin >> s1 >> s2;

    for(int i=0; i<=x; i++)
    {
        for(int j=0; j<=y; j++)
        {
            visited[i][j] = false;
        }
    }

    cout << lcs(0, 0);
    return 0;
}

longest common subsequence

int maxSubsequenceSubstring(char x[], char y[], 
                            int n, int m) 
{ 
    int dp[MAX][MAX]; 
  
    // Initialize the dp[][] to 0. 
    for (int i = 0; i <= m; i++) 
        for (int j = 0; j <= n; j++) 
            dp[i][j] = 0; 
  
    // Calculating value for each element. 
    for (int i = 1; i <= m; i++) { 
        for (int j = 1; j <= n; j++) { 
  
            // If alphabet of string X and Y are 
            // equal make dp[i][j] = 1 + dp[i-1][j-1] 
            if (x[j - 1] == y[i - 1]) 
                dp[i][j] = 1 + dp[i - 1][j - 1]; 
  
            // Else copy the previous value in the 
            // row i.e dp[i-1][j-1] 
            else
                dp[i][j] = dp[i][j - 1]; 
        } 
    } 
  
    // Finding the maximum length. 
    int ans = 0; 
    for (int i = 1; i <= m; i++) 
        ans = max(ans, dp[i][n]); 
  
    return ans; 
}

longest common subsequence

#include <bits/stdc++.h>

using namespace std;
int LCS(string s1,string s2,int n,int m)
{
    int dp[n+1][m+1];
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(i==0||j==0)
            {
                dp[i][j]=0;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(s1[i]==s2[j])
            {
                dp[i][j]=1+dp[i-1][j-1];
            }
            else
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    return dp[n][m];
}
int main()
{
    string s1,s2;
    cin>>s1>>s2;
    int n=s1.size();
    int m=s2.size();
    cout<<LCS(s1,s2,n,m);
    return 0;
}

longest common subsequence algorithm

#include<iostream>
using namespace std;
int LCS(string s1,string s2,int n1,int n2)
{
    int dp[n1+1][n2+1],i,j;
    for(i=0;i<n1+1;i++) dp[i][0]=0;
    for(j=0;j<n2+1;j++) dp[0][j]=0;
    for(i=1;i<n1+1;i++)
    {
        for(j=1;j<n2+1;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]);
        }
    }
    return dp[n1][n2];
}
int main()
{
    string s1,s2;
    int n1,n2;
    cin>>s1>>s2;
    n1 = s1.length();
    n2 = s2.length();
    cout<<LCS(s1,s2,n1,n2)<<endl;
}