LCSアルゴリズムの適応

Question

新しいプログラマーはここにあります。私は、LCS（最も長い共通部分文字列）の再帰アルゴリズムを表示するビデオを見ました。プログラムは、2つの文字列の間のLCSの長さであるintを返しただけです。文字列自体を返すようにアルゴリズムを適合させる練習として決めました。ここで私が思いついたのは正しいと思われますが、バグがあれば他の人にもっと尋ねる必要があります。

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文字までのサイズの2つの文字列に対してそれぞれ機能するようです。

バグとは何ですか？同様のダイナミックプログラミングソリューションは、同じ結果に対してより高速でメモリを少なくしますか？

おかげ

Answer 1

1. あなたのプログラムが正しくありません。 LCSnum（ "aba"、 "abba"）では何が返されますか？

2. string soFar[mAX][mAX]これは素晴らしい解決策ではないというヒントになるはずです。単純なダイナミックプログラミングソリューション（ほとんどのロジックがあります）は、サイズがm * nのsize_tの配列を持ち、bool Get[mAX][mAX]もありません。 （よりよい動的プログラミングアルゴリズムはわずか2 *分（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; 
    } 
}