6

シーケンスSのいくつの異なるサブシーケンス（必ずしも連続している必要はない）が値p0の特定のプロパティPを持っているかを尋ねる動的計画問題を考えてみましょう。

Pの範囲は小さく有限であり、Pを計算する効率的な方法があります。

P(s1 + s2) = f(P(s1), P(s2))

ここで、+はシーケンスの連結を示します。

これを行う1つの方法は、S[1] + S[2] + ... + S[k]プロパティpxを持つSのプレフィックスのサブシーケンスがいくつあるかを数えることです。（これをに保存しますCount[px][k]）

したがって、再帰は次のようになります。

Count[px][k] = Count[px][k-1] // not using element S[k];

P pq = f(px,P(S[k])); // calculate property pq of appending element S[k]
Count[pq][k] += Count[px][k-1] // add count of P(prefix+S[k])

そして答えは次のとおりです。

return Count[p0][S.length]

これは、Sの要素がペアごとに異なる場合に機能しますが、値は等しいが位置が異なる異なる要素を使用するサブシーケンスを2回カウントします。

このアルゴリズムを変更して、等しいサブシーケンスを1回だけカウントするようにするにはどうすればよいですか？（つまり、個別のサブシーケンスのみをカウントします）

4

1 に答える 1

3

シーケンスが文字であり、S[k]が文字xであるとします。

問題は、S [k]を使用しないすべてのシーケンスを二重にカウントしたが、それでもxで終了することです（これは、xがシーケンスの前半で発生した場合にのみ発生する可能性があります）。

xが最後に出現したのが要素S[j]であったと仮定します。xで終わるすべての個別のシーケンスは、位置j-1までのすべての個別のシーケンスをカウントし、これらすべてにxを加算することによって簡単に与えられます。

したがって、このカウントを引くことにより、二重カウントを修正できます。

Count[px][k] = Count[px][k-1] // not using element S[k]
P pq = f(px,P(S[k])) // property pq of appending element S[k]
j = index of previous location in string where S[j]==S[k]
Count[pq][k] += Count[px][k-1] // using element S[k]
Count[pq][k] -= Count[px][j-1] // Removing double counts
于 2012-08-01T18:59:32.417 に答える