Question

5. Find the longest common sequence between "ababba" and "aabaa" 15 points (Dynamic Programming)

Answer 1

/*If you have any query do comment in the comment section else like the solution*/

#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;
}

Output:

E:\CodeBlocks\Chegg\LongestCommonSubsequence.exe ababba aabaa 4 Process returned @ (exe) Press any key to continue. execution time : 19.187 s

b о a С a a 0 0 o 1 L 1 1 1 2 2 2 L 2 2 3 a o 3 3 3 bo 2 2 3 3 3 3 bo all 2 3 a o