Longest Common Subsequence top-bottom

Question

#include <iostream>
#include <cstring>
using namespace std;

int LCS(string x, string y , int n , int m)
{
  int t[n+1][m+1];
  for(int i=0;i<=n+1;i++)
    for(int j=0;j<=m+1;j++)
    {
        if(i==0 || j==0)
            t[i][j]=0;
    }
  for(int i=1;i<=n+1;i++)
    for(int j=1;j<=m+1;j++)
    {
        if(x[i-1]==y[j-1])
            t[i][j]=1+t[i-1][j-1];
        else
            t[i][j]=max(t[i-1][j],t[i][j-1]);
    }
  return t[n][m];
}

int main()
{
    string x;
    string y;
    cin>>x>>y;
    LCS(x,y,x.length(),y.length());
    return 0;
}

o/p=Process returned 0 (0x0) execution time : 3.342 s Press any key to continue.

the o/p to the following code is always zero . idk why. plzz help . what wrong am I doing ?

If you search for "longest common subsequence c++" in your favorite search-engine you will find many thousands of links, if not hundreds of thousands. Quite a few of them to questions here on Stack Overflow. In short, there are many tutorials and examples and answers to this question already. — Some programmer dude, Jun 29 '20 at 11:41
As for your problem, it seems like it's independent of the assignment or exercise, and is probably because your `main` function does (unconditionally) do `return 0`. Do note that the returned value from `main` is by convention a *small* non-negative integer (in the range `0` to `255`, inclusive), and that anything but `0` is considered an error. In short: You never use the value that `LCS` returns. — Some programmer dude, Jun 29 '20 at 11:48

bruno · Accepted Answer · 2020-06-29T12:37:09.013

0

the o/p to the following code is always zero

because your main does :

...
LCS(x,y,x.length(),y.length());
return 0;

but you want :

...
return LCS(x,y,x.length(),y.length());

Out of that

 int t[n+1][m+1];

is a variable length array, do not use them (see Why aren't variable-length arrays part of the C++ standard?) but array dynamically allocated in the heap, because the size are not known at compile time you can use a std::vector<std::vector<int>> and for instance replace

 int t[n+1][m+1];
 for(int i=0;i<=n+1;i++)
   for(int j=0;j<=m+1;j++)
   {
       if(i==0 || j==0)
           t[i][j]=0;
   }

by

  std::vector<std::vector<int>> t(n+1);
  
  for (int i = 0; i <= n; ++i)
    t[i].resize(m+1);

BTW your loops are wrong because the right tests are i<=nand j<=m everywhere

edited Jun 29 '20 at 12:37

answered Jun 29 '20 at 11:44

bruno

32,421
7
25
37

`std::array` is automatically allocated (i.e. on the stack). `std::vector` woule be for dynamic allocation. – underscore_d Jun 29 '20 at 11:53
The question is what you are talking about. If the OP wants runtime dimensions, then they cannot use `std::array`, because it's size is a compile-time constant, and it gets stored on the stack, with the data right inside itself. It is not allocated on the heap (unless one does something daft like allocating a pointer to an `std::array`, but even that still must have compile-time size). – underscore_d Jun 29 '20 at 12:00
@underscore_d ah yes damned – bruno Jun 29 '20 at 12:04
what changes should I do? – aniket sagar Jun 29 '20 at 12:06
@aniketsagar I just edited my answer, you can use a `std::vector>` – bruno Jun 29 '20 at 12:07
can u edit code and post it. am not able to get what to do. am new to StackOverflow community. – aniket sagar Jun 29 '20 at 12:20

Longest Common Subsequence top-bottom

1 Answers1