Адаптация алгоритма 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 символа в каждой.

Каковы ошибки и будет ли эквивалентное решение для динамического программирования быстрее или использовать меньше памяти для того же результата?

Спасибо

Answer 1

1. Ваша программа неверна. Что он возвращает для LCSnum ("aba", "abba")?

2. string soFar[mAX][mAX] должно быть намеком на то, что это не лучшее решение. Простое решение для динамического программирования (которое имеет логику, которой вы почти придерживаетесь) имеет массив size_t размером m * n и без 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;
    }
}