1

現在、特定の 2 つの文字列の最長の共通サブシーケンスを見つけて出力しようとしています。再帰なしで最も一般的なアルゴリズムを使用します。配列全体を保持する場合は簡単な作業ですが、少し最適化して 2 行のみを使用しようとしています。以下のコードで確認できます。この変更により、長さの検出は依然として簡単で正常に機能しますが、サブシーケンスの回復はそれほど簡単ではなくなりました。私はいくつかの方法でそれをやろうとしましたが、どちらもうまくいきませんでした。以下に、私の最後の試みを示します。同じケースで動作しますが、失敗するケースもあります。長い間考えた後、2行しかない配列を使用してサブシーケンスを回復する方法はないと信じ始めています。私の研究では正確な答えが得られなかったので、私が何を達成する方法があるか尋ねています。しようとしていますか？または、印刷したい場合、配列全体を保持することにこだわっていますか?

//finding length of longest common subsequence
for(int i=1; i<m; i++) {
    for(int j=1; j<n; j++) {
        if(sequece1[i-1] == sequence2[j-1]) {
            tab[i%2][j] = tab[(i-1)%2][j-1] + 1;
        } else {
            tab[i%2][j] = max(tab[i%2][j-1],tab[(i-1)%2][j]);
        }
    }
}

//trying to reconstruct longest common subsequence
int last_row = (m-1)%2;
for(int j=n-1; j>0; j--) {
    if(tab[last_row][j-1] < tab[last_row][j]) {
        if(last_row == 0) {
            common_part += sequence2[j];
            } else {
            common_part += sequence2[j-1];
        }
    }
}
4

1 に答える 1

1

最後の 2 つの列だけを保持すると、情報の本質的な部分が失われるため、これを達成する簡単な方法はないようです。

たとえば、( , ) 文字列と ( , ) 文字列の 2 つのケースを考えてabccみaccましょabccうbcc。これらの場合のマトリックスは次のようになります。

1 1 1 1    and  0 1 1 1
1 1 2 2         0 1 2 2
1 1 2 3         0 1 2 3

最後の 2 列はどちらの場合も同一であることがわかります。したがって、最後の 2 列だけで判断してこれらのケースを区別することはできません。ただし、答えが異なるため (accとbcc)、それらを区別する必要があります。もちろん、元の文字列はまだ残っており、そこからの情報を使用できますが、これは元の文字列のいくつかのプレフィックスの LCS を見つけることと多かれ少なかれ同等だと思います (証明はしていませんが)。

同時に、二次時間と線形空間で機能するより高度なアルゴリズムがあります。

于 2015-04-22T18:17:27.190 に答える