1

これら 2 つの文字列 {xaybadfeg, abcdefg} の最長の共通サブシーケンスは何ですか? 「アブデグ」じゃない？私はこのアルゴリズム (動的計画法) を使用して解決策を見つけています。答えとして「adeg」を返します。subsequence の私の理解は間違っていますか? 私のアルゴリズムは間違っていますか？何か不足していますか？このタイプの入力をコーナーケースにする必要がありますか?

動的プログラミング コード

#include <iostream>
#include <stack>
using namespace std;

void LCS(string str1, string str2){
    int out[100][100] = {};
    for (int i = 0; i <= str1.size(); i++){
        for (int j = 0; j <= str2.size(); j++){
            if (i == 0 || j == 0)
                out[i][j] = 0;
            else{
                if (str1[i-1] == str2[j-1]){
                    if (out[i][j - 1] > out[i - 1][j])
                        out[i][j] = out[i][j - 1] + 1;
                    else
                        out[i][j] = out[i - 1][j] + 1;
                }
                else{
                    if (out[i][j - 1] > out[i - 1][j])
                        out[i][j] = out[i][j - 1];
                    else
                        out[i][j] = out[i - 1][j];
                }
            }
        }
    }

    //Backtracing to print the numbers
    int i = str1.size()-1, j = str2.size()-1;
    std::string subSeqStr="";
    while (i >= 0 || j >= 0){
        if (str2[j] != str1[i]){
            if (out[i][j - 1] > out[i - 1][j])
                j--;
            else
                i--;
        }
        else{
            subSeqStr.insert(subSeqStr.begin(), str2[j]);
            i--; j--;
        }
    }
    std::cout << "The least common subsequence is: " << subSeqStr<< std::endl;
}

int main(){
    string str1 = "xaybadfeg";
    string str2 = "abcdefg";
    LCS(str1,str2);
    getchar();
    return 0;
}

どんな入力でも大歓迎です。ありがとう！

4

2 に答える 2

1

「abdeg」は最も長い一般的なサブシーケンスですが、「abdfg」のようなものもあります。

バックトラックは間違っています。i と j の値を出力すると、負の値になり、無効な文字列インデックスがアクセスされます。

文字列インデックスから 1 を引くと、正しい答えが得られます。|| も変更しました。条件を && にします。

int i = str1.size(), j = str2.size();
std::string subSeqStr="";
while (i > 0 && j > 0){
    if (str2[j - 1] != str1[i - 1]) {
        if (out[i][j - 1] > out[i - 1][j])
            j--;
        else
            i--;
    }
    else{
        subSeqStr.insert(subSeqStr.begin(), str2[j - 1]);
        i--; j--;
    }
}
于 2016-07-09T20:37:40.413 に答える
0

これは間違っているように見えます:

if (i == 0 || j == 0)
    out[i][j] = 0;

文字列には 0 からインデックスが付けられているため、インデックスを 1 から開始すると見なしているほとんどの教科書やチュートリアルに表示される式を適用することはできません。

最も簡単な方法は、おそらく文字列の前に何かを追加することです。そのため、インデックスも 1 から開始します。そうしないと、式に見苦しい調整を加える必要があります。

于 2016-07-09T20:10:24.000 に答える