longest common subsequence using memoization

Question

This program is of longest common subsequence using memoization. But it is giving answer 0 for the below example. Before adding memoization, it was giving correct answer 2.

I think I did mistake in adding memoization. Can anyone help me with what is wrong with this code?

#include<bits/stdc++.h>
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
 char a[100]="bd",b[100]="abcd";
 int lcs1[100][100];

 int lcs(int i,int j){
     int temp;
     if(lcs1[i][j]!=-1)

     if(a[i]=='\0'||b[i]=='\0'){
        return 0;
     }
     if(lcs1[i][j]!=-1)
        return lcs1[i][j];
     else if (a[i]==b[j])
        temp = 1+lcs(i+1,j+1);
     else
        temp = max(lcs(i+1,j),lcs(i,j+1));
     lcs1[i][j] = temp;
     return temp;

 }
 int main(){

     int temp = lcs(0,0);
     memset(lcs1,-1,sizeof(lcs1));
     printf("%d",temp);

 }

Welcome to SO! I recommend cleaning up to your code to use spacing between operators and braces for your conditionals (which appears to be the cause of one of your logic errors). — ggorlen
– ggorlen, Commented Dec 29, 2018 at 19:24

Georgi Gerganov · Accepted Answer · 2018-12-29 20:09:31Z

1

2 problems:

you were initialising the memoization array after calling lcs()
you had an extra if in the beginning of your lcs()

Here is corrected code:

#include<cstring>
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
 char a[100]="bd",b[100]="abcd";
 int lcs1[100][100];

 int lcs(int i,int j){
     int temp;
     //if(lcs1[i][j]!=-1)       // problem 2

     if(a[i]=='\0'||b[i]=='\0'){
        return 0;
     }
     if(lcs1[i][j]!=-1)
        return lcs1[i][j];
     else if (a[i]==b[j])
        temp = 1+lcs(i+1,j+1);
     else
        temp = max(lcs(i+1,j),lcs(i,j+1));
     lcs1[i][j] = temp;
     return temp;

 }
 int main(){
     memset(lcs1,-1,sizeof(lcs1));  // problem 1
     int temp = lcs(0,0);
     printf("%d",temp);

 }

_{Note: that it is a good practice to avoid global variables. Try to capsulate them in structures or classes. See @Matthieu Brucher's answer for proper C++ implementation.}

edited Dec 29, 2018 at 20:09

answered Dec 29, 2018 at 19:24

Georgi Gerganov

1,0869 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Matthieu Brucher Over a year ago

Please, no answer with #include <bits/c++.h>. Same for all these global variables or C headers.

Georgi Gerganov Over a year ago

Fixed. Mind if I ask why we should avoid this header?

Matthieu Brucher Over a year ago

Because it's an implementation detail of libstdc++. There are many answers about this on SO.

Georgi Gerganov Over a year ago

Thanks. I agree global variables are bad. Should I just remove the corrected code and leave the description of the 2 problems I found ?

Matthieu Brucher Over a year ago

Let's say that you should at least give a disclaimer saying that this is far from being proper C++ code.

Matthieu Brucher · Accepted Answer · 2018-12-29 19:48:48Z

Just for fun, a C++17 implementation with classes:

#include <iostream>
#include <vector>
#include <string_view>

class LCSMemoizer
{
    std::vector<std::vector<int>> memory;
    std::string_view s1;
    std::string_view s2;

public:
    LCSMemoizer(std::string_view s1, std::string_view s2)
    : memory(s1.size(), std::vector<int>(s2.size(), -1)), s1(s1), s2(s2)
    {
    }

    int run(unsigned int i1, unsigned int i2)
    {
        if(i1 == s1.size() || i2 == s2.size())
        {
            return 0;
        }
        if(memory[i1][i2] != -1)
        {
            return memory[i1][i2];
        }
        int sub = 0;
        if(s1[i1] == s2[i2])
        {
            sub = run(i1+1, i2+1);
            sub += 1;
        }
        else
        {
            sub = std::max(run(i1, i2+1), run(i1+1, i2));
        }
        memory[i1][i2] = sub;
        return sub;
    }
};

int lcs(std::string_view s1, std::string_view s2)
{
    LCSMemoizer m(s1, s2);

    return m.run(0, 0);
}

int main()
{
    std::cout << lcs("bd", "abcd");
}

Also note that the usual question is not just to return the count, but also the string itself.

Collectives™ on Stack Overflow

longest common subsequence using memoization

2 Answers 2

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related