Adaptation of LCS algorithm

new programmer here. I watched a video which displayed a recursive algorithm for LCS(longest common substring). The program only returned an int which was the length of th开发者_开发问答e LCS between the two strings. I decided as an exercise to adapt the algorithm to return the string itself. Here is what I came up with, and it seems to be right, but I need to ask others more experienced if there are any bugs;

const int mAX=1001; //max size for the two strings to be compared
string soFar[mAX][mAX]; //keeps results of strings generated along way to solution
bool Get[mAX][mAX]; //marks what has been seen before(pairs of indexes)

class LCS{ //recursive version,use of global arrays not STL maps
private: 
public:
 string _getLCS(string s0,int k0, string s1,int k1){
  if(k0<=0 || k1<=0){//base case
   return "";
  }  
  if(!Get[k0][k1]){ //checking bool memo to see if pair of indexes has been seen before
   Get[k0][k1]=true; //mark seen pair of string indexs
   if(s0[k0-1]==s1[k1-1]){
    soFar[k0][k1]=s0[k0-1]+_getLCS(s0,k0-1,s1,k1-1);//if the char in positions k0 and k1 are equal add common char and move on
   }
   else{
    string a=_getLCS(s0,k0-1,s1,k1);//this string is the result from keeping the k1 position the same and decrementing the k0 position
    string b=_getLCS(s0,k0,s1,k1-1);//this string is the result from decrementing the k1 position keeping k0 the same
    if(a.length()> b.length())soFar[k0][k1]=a;//the longer string is the one we are interested in
    else
     soFar[k0][k1]=b;
   }
  } 
  return soFar[k0][k1];
 }
 string LCSnum(string s0,string s1){
  memset(Get,0,sizeof(Get));//memset works fine for zero, so no complaints please
  string a=_getLCS(s0,s0.length(),s1,s1.length());
  reverse(a.begin(),a.end());//because I start from the end of the strings, the result need to be reversed
  return a;
 }
};

I have only been programming for 6 months so I cant really tell if there is some bugs or cases where this algorithm will not work. It seems to work for two strings of size up to 1001 chars each.

What are the bugs and would the equivalent dynamic programming solution be faster or use less memory for the same result?

Thanks

1. Your program is not correct. What does it return for LCSnum("aba", "abba")?

2. string soFar[mAX][mAX] should be a hint that this is not a great solution. A simple dynamic programming solution (which has logic that you almost follow) has an array of size_t which is m*n in size, and no bool Get[mAX][mAX] either. (A better dynamic programming algorithm only has an array of 2*min(m, n).)

Edit: by the way, here is the space-efficient dynamic programming solution in Java. Complexity: time is O(m*n), space is O(min(m, n)), where m and n are the lengths of the strings. The result set is given in alphabetical order.

import java.util.Set;
import java.util.TreeSet;

class LCS {
    public static void main(String... args) {
        System.out.println(lcs(args[0], args[1]));
    }

    static Set<String> lcs(String s1, String s2) {
        final Set<String> result = new TreeSet<String>();

        final String shorter, longer;
        if (s1.length() <= s2.length()) {
            shorter = s1;
            longer = s2;
        }else{
            shorter = s2;
            longer = s1;
        }

        final int[][] table = new int[2][shorter.length()];
        int maxLen = 0;

        for (int i = 0; i < longer.length(); i++) {
            int[] last = table[i % 2]; // alternate
            int[] current = table[(i + 1) % 2];
            for (int j = 0; j < shorter.length(); j++) {
                if (longer.charAt(i) == shorter.charAt(j)) {
                    current[j] = (j > 0? last[j - 1] : 0) + 1;

                    if (current[j] > maxLen) {
                        maxLen = current[j];
                        result.clear();
                    }
                    if (current[j] == maxLen) {
                        result.add(shorter.substring(j + 1 - maxLen, j + 1));
                    }
                }
            }
        }

        return result;
    }
}