3

一般的な LCS 問題とアルゴリズムを知っています。

こんな感じです：

LCS(Xi, Yj) = [0 (i = 0 or j = 0)
           or LCS(Xi-1, Yj-1) + 1 (xi = yj)
           or max(LCS(Xi, Yj-1), LCS(Xi-1, Yj)) (xi != yj)]

しかし、ギャップ条件を追加するとどうなるでしょうか。

例えば：

String A is cttauaucagu
String B is cautauatcgu

if no gap condition
lcs = cauauagu

if gap = 1 (lcs gap is under 1)
lcs = auaua

if gap = 0 (lcs gap is under 0)
lcs = taua

視覚的表現:

これを解決するにはどうすればよいですか？

DP テーブルの作成方法を教えてください。

4

1 に答える 1

4

この場合の解決策はそれほど変わりません。別の 2 つのパラメーターを dp に追加する必要があります。これは、両方の文字列の共通サブシーケンスに含まれる最後の要素のインデックスです。次に、dp の各ステップで、指定された文字列の the_last_included_element と the_last_included_element + gap + 1 の間で等しい要素のみを検索します。

于 2013-10-08T12:25:45.520 に答える