1

ある長さNの「ターゲット文字列」（またはリスト、実際には重要ではない）があるとしましょう。簡単にするために、「A」と「B」の2つの可能な文字だけがあるとしましょう。したがって、たとえば、ターゲット文字列は「ABBABB」である可能性があります。

次に、ある長さ<= Nのテスト文字列が与えられます（ここでも、同じ2つの可能な文字）。正当な変換は文字の挿入だけであるという制約の下で、テスト文字列をターゲット文字列に変換できるかどうかを判断したいと思います。

たとえば、ターゲットがABBABBで、テストがBBBであるとします。その場合、答えは「はい」です。テストをターゲットに変換できます。例：BBB-> BBAB->ABBAB->ABBABB。

ただし、テストがBABAの場合、ターゲットはAで始まるため、ターゲットに変換できません。テストは機能しません。また、Aをテストに挿入すると、Aが増えるため、機能しません。ターゲットが持っているよりも。

明らかに、私はブルートフォースによってこれを「はい」または「いいえ」で判断し、可能なすべての文字挿入シーケンスを実行することができました。しかし、もっと効率的な方法はありますか？

前もって感謝します。

4

3 に答える 3

7

一見すると、簡単な答えは、テスト文字列がターゲット文字列に順番に含まれている場合、テストに合格するということのようです。

何かのようなもの：

int i = 0;
foreach (char c in target) {
    if (i == test.Length) return true; // Found all test chars
    if (test[i] == c) {
        i++; // found this test char; check for next
        if (i == test.Length) break;
    }
}
return i == test.Length; // Found all test chars
于 2012-04-20T21:08:02.750 に答える
1

これを解決するには、動的計画法を使用できます。X を最初の文字列、Y を最後の文字列とします。逆の問題、つまり Y から削除して、X を取得できるかどうかを見てみましょう。

F(Y,X) = (if X[0]=Y[0]: F(X[1:],Y[1:] ) or F(Y[1:],X)

終了条件:If X='', return True elsif Y='' return False

すべての動的計画問題と同様に、len(X)*len(Y) の異なる (i,j) の組み合わせに対して F(X[i:],F[j:]) を計算して保存する必要があることに注意してください。

于 2012-04-20T20:44:22.297 に答える
0

1) テスト/ターゲット文字列を配列に変換します。各要素は、接続された "A" と "B" の数を表すペアです。

例: ABBABB ==> { (1,2) (1,2) }; BBB ==> { (0,3) }; ババ ==> { (0,1) (1,1) (1,0) }

2) 次を含む要素レベルを定義: a>=c および b>=d の場合、P1 (a,b) は P2 (c,d) を含む

2 つの要素 P1 (a,b) と P2 (c,d) に対して 2 つの操作を定義します。

mergeA(P1,P2) ==> (a+c,d);

mergeB(P1,P2) ==> (a,b+d)

3) 抽象化された問題があります: テスト配列 {T1, T2, ..., Tn} とターゲット配列 {A1, A2, ... Am} が与えられた場合、ターゲット配列にテスト配列が含まれているかどうかを示します。ここで「contain」は再帰的に定義できます。

i の場合、ターゲット配列にはテスト配列が含まれます。ターゲット配列には、テスト配列と同じかそれ以上の要素があります。ii. [1,m] の各 i に対して、Ai に Ti が含まれる

また

mergeA(A1,A2), A3, A4 ... にはテスト配列が含まれます

また

mergeB(A1,A2), A3, A4 ... にはテスト配列が含まれます

4) 疑似コード

bool ifContain(Pair[] target, Pair[] test) {
    if (test.length>target.length) return false;
    if (test.length()==1) 
        return (target.A>=test.A && target.B>=test.B);
    return   (ifContain(target[0], test[0]) && ifContain(targe(1,:),test(1,:)))
        || ifContain(Pair(target[0].a,target[0].b+target[1].b)+target(2,:),test)
        || ifContain(Pair(target[0].a+target[1].a+target[1].b)+target(2,:),test);
}
于 2012-04-20T21:56:45.040 に答える