LCS算法的自适应

Question

新来的程序员。我看了一段视频，其中显示了LCS(最长公共子串)的递归算法。程序只返回一个int，它是两个字符串之间LCS的长度。作为一项练习，我决定调整算法以返回字符串本身。这是我想出来的，它似乎是正确的，但我需要问其他更有经验的人，如果有任何错误；

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

我只编程了6个月，所以我不知道是否有一些错误或情况下，这一算法将无法工作。它似乎适用于两串大小高达1001个字符的字符串。

什么是bug，等效的动态规划解决方案会更快，还是为相同的结果使用更少的内存？

谢谢

Answer 1

1. 您的程序不正确。它返回什么LCSnum("aba"，"abba")?
2. string soFar[mAX][mAX]应该是一个提示，这不是一个很好的解决方案。一个简单的动态编程解决方案(具有几乎遵循的逻辑)有一个大小为m*n的size_t数组，也没有bool Get[mAX][mAX]。(一个更好的动态规划算法只有2*min(m，n)的数组)

。

编辑:顺便说一句，这里是Java中的空间高效动态编程解决方案。复杂性:时间是O(m*n)，空间是O(min(m，n))，其中m和n是字符串的长度。结果集按字母顺序给出。

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