1

ここ数時間、Longest Common Subsequence を実装しようとしています。LCSLength 関数が正しい長さを返すことを確認しましたが、シーケンスが正しく出力されません。 

int max(int a , int b)
{
    if(a>b) 
        return a;
    else 
        return b;
}
/* The printing function that is not functioning Properly */
string backtrack(vector< vector<int> > C, string X,string Y,int i,int j)
{
    if( i==0  || j==0)
        return "";
    else if( X[i] == Y[j])
        return backtrack(C,X,Y,i-1,j-1) + X[i];
    else
        if( C[i][j-1] >= C[i-1][j] )
            return backtrack(C,X,Y,i,j-1);
        else
            return backtrack(C,X,Y,i-1,j);

}



   /* It correctly returns the subsequence length. */
   int LCSLength(string s1,string s2)
   {   
        vector< vector <int> >  C (s1.size()+1 , vector<int> (s2.size() +1 ) );
        int i,j;
        int m = s1.size();
        int n = s2.size();
        for(i =0; i<=m; i++){
        for( j =0; j<=n; j++){
            if( i==0 || j==0)
                C[i][j] = 0;
            else if( s1[i-1] == s2[j-1] )
                C[i][j] = C[i-1][j-1] +1;
            else
                C[i][j] = max(C[i][j-1],C[i-1][j]);
        }
    }




    cout << backtrack(C,s1,s2,m,n);


    return C[m][n];
}

ここにある疑似コードに従っています: http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

任意の助けをいただければ幸いです。

テストされたケース:

 cout << LCSLength("HUMAN", "CHIMPANZEE") << endl;

4 を返しますが、文字列シーケンスが正しくありません。

  cout << LCSLength("AAACCGTGAGTTATTCGTTCTAGAA","CACCCCTAAGGTACCTTTGGTTC") << endl;

14を返します

ありがとう。

4

1 に答える 1

2

あなたの停止条件は次のとおりであるため、私はそれを推測しています：

if( i==0  || j==0)
     return "";

X[0] または Y[0] にあるキャラクターに到達することはできません。H が最初の文字であるため、間違った出力 (「HMAN」ではなく「MAN」) の例はこれと一致します。

リンクする wiki 値は、文字列を として定義していることに注意してくださいX[1..m] and Y[1..n]。これは、おそらく c++ でこれを行う直感的な方法ではありません。

停止条件として -1 に切り替えるか、最初に文字列をパディングしてみてください。

于 2013-11-12T21:46:39.190 に答える