17

A長さ N の文字列とB長さ M の文字列 (M < N) がある場合、文字列が の部分文字列として発生しないAように、文字列から削除する必要がある文字の最小数をすばやく計算できますか?BA

文字列の長さが小さい場合、この問題は非常に簡単に力ずくで解決できます。ビットマスクを0toから反復し、 の部分列の部分文字列として発生する2^Nかどうかを確認するだけです。ただし、N が最大 10,000 になり、M が最大 1,000 になると、このアルゴリズムは明らかにすぐに崩壊します。これを行うより速い方法はありますか？BA

例: A= ababaaB= aba. Answer= 1.A の 2 番目aを削除するとabbaa、 が含まれない になりますB。

編集:ユーザー nm が素晴らしい反例を投稿しました: aabccand abc. またはをb削除すると文字列の別のインスタンスが作成されるため、単一の を削除します。acabc

4

5 に答える 5

0

これが私が思いついたスケッチです。

まず、A に B にない記号が含まれている場合、A を分割して、B にある文字のみを含む一連の小さな文字列にします。小さな文字列のそれぞれにアルゴリズムを適用し、それらを再び接着して合計を取得します。結果。これは実際には最適化として機能します。

次に、A に B のいずれかが含まれているかどうかを確認します。含まれていない場合は、完了です。A = B の場合、それらをすべて削除します。

比較的貪欲なアルゴリズムが機能する可能性があると思います。

最初に、少なくとも 1 回の B の発生に属する A 内のすべての記号をマークします。A = aabcbccabcaa、B = abc とします。太字は、これらのマークされた文字を示します。

a abc bcc abc aa. 重複がある場合は、可能なものすべてに○をつけてください。この操作は単純に近似 (AB) 操作ですが、ほぼ (A/B) 操作で実行できると思います。

A でマークされた各文字を削除することを検討してください: a abc bcc abc aa.

そのマークされた文字を削除すると、マークされた文字の数が減少するかどうかを確認します。文字の削除によって影響を受ける可能性のある部分文字列のみを確認する必要があります。B の長さが 4 の場合、x がチェックされている場合、次の場所で始まる部分文字列のみを削除する必要があります。

-------x------
    ^^^^

x の存在に関係なく、さらに左または右が存在します。

例えば：

次の文字列の [a] をマーク: a [a]bc bcc abc aa.

これを削除すると abcbccabcaa が生成され、マークを付けるとabc bcc abc aa が生成され、マークされた文字の数は同じになります。この操作には相対数のみが必要なため、選択した文字ごとに約 2B の時間で実行できます。それぞれについて、2 つの間の相対的な差を割り当てます。最大のものを任意に選んで削除します。完了するまで繰り返します。各パスは、最大 A パスの場合、およそ 2AB までの操作であり、合計時間は約 2A^2 B になります。

上記の例では、次の値が割り当てられています。

aabcbccabcaa
 033   333

したがって、最初にマークされた b を任意に削除すると、aacbccabcaa が得られます。このプロセスを繰り返すと、次のようになります。

aacbccabcaa
      333

最終結果が完成しました。

アルゴリズムは正しく最小であると思います。A が 1 つの削除のみを必要とするときはいつでも、アルゴリズムは最適でなければならないというのは本当だと思います。その場合、一致する可能性が最も高い文字 (つまり、すべての文字) が最適です。しかし、私はそのような証拠を思いつくことはできません。最適性の反例を見つけることに興味があります。

于 2013-10-10T22:19:20.963 に答える
0

文字列 でグラフ検索を実行できますかA。これは、大きな N と特別な入力にはおそらく遅すぎますが、指数関数的なブルート フォース アルゴリズムよりはうまく機能するはずです。たぶんBFS。

于 2013-03-10T02:55:46.930 に答える
0

この質問がまだ誰かの興味を引いているかどうかはわかりませんが、うまくいくかもしれないという考えがあります。

問題は部分文字列を見つけることではなく、文字列 A からどの文字を削除するのがより便利かを判断することであると判断したら、解決策は非常に単純に見えます。できることは、文字列内にあり、右側のボンダリに閉じている文字を削除することです...最後の前のものとしましょう。そのため、実際に開始方法を終了する部分文字列がある場合、最初の char を削除すると、B 出現の 1 つを削除するだけで、実際には一度に 2 つを削除できます。

疑似 cose のアルゴリズム:

String A, B;
int occ_posit = 0;
N = B.length();

occ_posit = A.getOccurrencePosition(B); // pseudo function that get the first occurence of B into A and returns the offset (1° byte = 1), or 0 if no occurence present.

while (occ_posit > 0)  // while there are B into A
{
    if (B.firstchar == B.lastchar)  // if B starts as it ends
    {
        if (A.charat[occ_posit] == A.charat[occ_posit+1])
            A.remove[occ_posit - 1]; // no reason to remove A[occ_posit] here
        else
            A.remove[occ_posit]; // here we remove the last char, so we could remove 2 occurencies at the same time
    }
    else
    {
        int x = occ_posit + N - 1;
        while (A.charat[x + 1] == A.charat[x])
            x--; // find the first char different from the last one

        A.remove[x]; // B does not ends as it starts, so if there are  overlapping instances they overlap by more than one char. Removing the first that is not equal to the char following B instance, we kill both occurrencies at once.
    }
}

例を挙げて説明しましょう：

A = "123456789000987654321" B = "890"

これを表として読んでください：

occ_posit:  123456789012345678901

       A = "123456789000987654321"
       B =        "890"

最初のオカレンスは occ_posit = 8 です。B は開始時に終了しないため、2 番目のループに入ります。

int x = 8 + 3 - 1 = 10;
while (A.charat[x + 1] == A.charat[x])
    x--; // find the first char different from the last one
A.remove[x];

while は、A.charat11 が A.charat[10] (="0") と一致することを検出するため、x は 9 になり、while は A.charat[10] が A.charat9 と一致しないため終了します。A は次のようになります。

A = "12345678000987654321"

それ以上のオカレンスはありません。

別のものを試してみましょう: A = "abcccccccccc" B = "abc"

最初のオカレンスは occ_posit = 1 です。B は開始時に終了しないため、2 番目のループに入ります。

int x = 1 + 3 - 1 = 3;
while (A.charat[x + 1] == A.charat[x])
    x--; // find the first char different from the last one
A.remove[x];

while は A.charat4 が A.charat[3] (="c") と一致することを検出するため、x は 2 になり、while は A.charat[3] が A.charat2 と一致しないため終了します。A は次のようになります。

A = "acccccccccc"

オーバーラップを試してみましょう:

A = "abcdabcdabff" B = "abcdab"

アルゴリズムの結果は次のとおりです。

最後に、1 つの文字が重なっています。

A = "アバババババ" B = "アバ"

B は開始時に終了するため、次の場合に最初に入ります。

if (A.charat[occ_posit] == A.charat[occ_posit+1])
            A.remove[occ_posit - 1]; // no reason to remove A[occ_posit] here
        else
            A.remove[occ_posit]; // here we remove the last char, so we could remove 2 occurencies at the same time

これにより、B インスタンスの最後の「a」を削除できます。そう：

1° ステップ: A= "abbbbabbbba" 2° ステップ: A= "abbbbabbbba" これで完了です。

お役に立てれば

編集：検索でAの終わりに近づいたときにエラーが発生しないように、アルゴリズムを少し修正する必要があることに注意してください。ただし、これは簡単なプログラミングの問題です。

于 2013-08-30T12:30:47.953 に答える