3

LCSの問題には時間が必要であることを知っています〜O（m n）ここで、mとnはそれぞれ2つのシーケンスXとYの長さです。しかし、私の問題は少し簡単なので、~O(m n) よりも高速なアルゴリズムを期待しています。

これが私の問題です：

入力：

正の整数 Q、2 つのシーケンス X=x1,x2,x3...xn および Y=y1,y2,y3...yn、両方とも長さ n。

出力：

X と Y の LCS の長さが少なくとも n - Q の場合は true。

そうでなければ、偽。

よく知られているアルゴリズムのコストはここでは O(n^2) ですが、実際にはそれよりも優れた処理を行うことができます。共通の要素を見つけることなく、いずれかのシーケンスで Q 個の要素を削除するたびに、結果は False を返すためです。O(Q*n) に匹敵するアルゴリズムがあるはずだと誰かが言っていましたが、私にはわかりません。

更新: すでに答えが見つかりました!

テーブル c[i,j] の対角ブロックを計算するだけでよいと言われました。なぜなら、|ij|>Q の場合、両方のシーケンスに一致しない要素が既に Q 個以上あることを意味するからです。したがって、|ij|<=Q の場合にのみ c[i,j] を計算する必要があります。

4

2 に答える 2

0

また、文字列を等しくするためのプロセスのコストが Q を超えてはならないということもできます。それが Q よりも大きい場合、答えは false でなければなりません。(EDIT DISTANCE PROBLEM)

文字列 x のサイズが m で、文字列 y のサイズが n であると仮定すると、2 次元配列 d[0..m][0..n] を作成します。ここで、d[i][j] は編集を示します。 x の i 長のプレフィックスと y の j 長のプレフィックスの間の距離。

配列 d の計算は、次の再帰を使用する動的計画法を使用して行われます。

d[i][0] = i , for i <= m
d[0][j] = j , for j <= n

d[i][j] = d[i - 1][j - 1], if s[i] == w[j],
d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + 1), otherwise.

LCSの答え if m>n, m-dp[m][m-n]

于 2014-10-15T09:56:30.717 に答える
0

これを行う方法の 1 つを次に示し
ます。 1. の要素が既に処理され、正確にそれらの要素が削除されたようなf(prefix_len, deleted_cnt)、 が の左端の位置であると仮定します。を超えることはできないため、明らかに状態しかありません。 2. 基本ケースは(何も処理されなかったため、何も削除されませんでした)。 3. トランジション: a) 現在の要素を削除します: . b) 現在の要素を、それと等しく、その後にある最も左にある可能性のある要素と一致させます ( index があると仮定しましょう): 。Yprefix_lenXdeleted_cntO(N * Q)deleted_cntQ
f(0, 0) = 0

f(i + 1, j + 1) = min(f(i + 1, j + 1), f(i, j))
Yf(i, j)posf(i + 1, j) = min(f(i + 1, j), pos)
4. したがって、残っている唯一の問題は、指定された位置から右にある左端の一致する要素を取得する方法です。次のペアを事前に計算してみましょう: (position in Y, element of ) -> のこの位置から右にある のこの要素に等しいXの要素の左端の発生。それらをハッシュ テーブルに入れます。のように見えます。しかし、そうではありません。の固定位置の場合、位置よりも右に移動する必要はありません。なんで？さらに進むと、以上の要素をスキップします! したがって、この事実を使用してペアのみを調べ、目的の時間計算量を得ることができます。このハッシュテーブルがあると、YXYO(n^2)YQ + 1QO(N * Q)posステップ 3 の間は、ハッシュ テーブルのルックアップが 1 回だけです。このステップの疑似コードは次のとおりです。

map = EmptyHashMap()
for i = 0 ... n - 1:
    for j = i + 1 ... min(n - 1, i + q + 1)
        map[(i, Y[j])] = min(map[(i, Y[j])], j)

残念ながら、このソリューションはハッシュ テーブルを使用するためO(N * Q)、最悪の場合ではなく、平均して時間の複雑さが生じますが、実行可能であるはずです。

于 2014-10-14T18:41:55.323 に答える