Program to print Longest Common Subsequence

[Ritik]

I found this implementation on a website for printing the longest common subsequence. But it gives wrong answers for some reason even though the code seems right to me.
Here is the code:

#include <iostream>


int lcs(char *X, char *Y, int m, int n)
{
  int L[m+1][n+1];
  for(int i = 0; i<=m; i++)
    {
      for(int j = 0; j<=n; j++)
	{
	  if(i==0 || j==0)
	    {
	      L[i][j] = 0;
	    }
	  else if(X[i-1] == Y[j-1])
	    {
	      L[i][j] = L[i-1][j-1] + 1;
	    }
	  else 
	    {
	      L[i][j] = std::max(L[i-1][j], L[i][j-1]);
	    }
	}
    }
  return L[m][n];
}

int main()
{
  int m;
  int n;
  char X[m], Y[n];
  std::cin >> m >> n;
  std::cout << "Enter the string X : ";
  for( int i = 0; i<m; i++)
    {
      std::cin >> X[i];
    }
  std::cout << "Enter the string Y : ";
  for(int j = 0; j<n; j++)
    {
      std::cin >> Y[j];
    }
  std::cout << std::endl;
  std::cout << "The length of the LCS is " << lcs( X, Y, m, n) << std::endl ;
  return 0;
}

What is wrong with this code?

[Yay295]

lines 30-33 shouldn't even compile. This looks like a program written in c and then 'ported' to c++, poorly. There are much better functions in c++ that could have been used for this.

[ne555]

  int m;
  int n;
  char X[m], Y[n];
  std::cin >> m >> n;

The array size should be known at compile time
There are some compiler extension that may allow you to do that, but it is not standard

You need to remember that the code executes sequentially from top to bottom. So at line 32 the values of `m' and `n' are uninitialized (they contain garbage). Then it's very likely that you are accessing them out of bounds.

[Yay295]

I wrote a working version.

or not

I will write a working version.

[cire]

Yay295 wrote:

I wrote a working version.

A "subsequence" need not consist of contiguous elements. std::string::find returning a non-zero value does not indicate success.

http://en.wikipedia.org/wiki/Subsequence
http://www.cplusplus.com/reference/string/string/find/

[helios]

I wrote this a while back as an experiment:
http://pastebin.com/dFcBhZFY

As an aside, I eventually gave up on my idea because, while LCS works flawlessly as a diff algorithm, its O(n*m) time is prohibitively expensive if you want to compare lists of millions of elements.

[Yay295]

I'm pretty sure I got it working correctly now:

#include <iostream>
#include <string>
#include <algorithm>


int main ( )
{
    std::string s1, s2;


    std::cout << "Enter the first string: ";

    std::cin >> s1;

    std::cout << "Enter the second string: ";

    std::cin >> s2;


    const size_t l1 = s1.length ( ), l2 = s2.length ( );

    std::string subsequence = "";


    for ( size_t start = 0; start < l1 && ( l1 - start ) > subsequence.length ( ); ++start )
    {
        std::string temp = "";

        size_t x, pos = 0;


        for ( size_t i = start; i < l1; ++i )
        {
            x = s2.find ( s1[i], pos );

            if ( x != -1 )
            {
                temp += s1[i];

                pos = x;
            }
        }


        if ( temp.length ( ) > subsequence.length ( ) )
            subsequence = temp;
    }


    std::cout << "Longest Subsequence: " << subsequence << "\nLength: " << subsequence.length ( ) << '\n';

    std::cin.ignore ( );
}

[helios]

Line 40 should be x + 1.

I don't think the outermost loop adds anything. You aren't going to find a longer subsequence by considering a shorter input.