3

サイズ m の文字のバッグB(マルチセット) とサイズ n の文字列テキスト S が与えられます。BS で (4!=24 の組み合わせ)によって作成できるすべての部分文字列を線形時間で見つけることは可能O(n)ですか?

例：

S = abdcdbcdadcdcbbcadc (n=19)
B = {b, c, c, d} (m=4)
Result: {cdbc (Position 3), cdcb (Position 10)}

私が見つけた最速の解決策は、各キャラクターのカウンターを保持し、各ステップでそれをバッグと比較することです。したがって、ランタイムはO(n*m). 必要に応じてアルゴリズムを表示できます。

4

3 に答える 3

4

長さ m の部分文字列のみに関心があると仮定すると、O(n) でそれを行う方法があります (それ以外の場合は不可能です。文字列内のすべての文字を含むバッグの場合、 s、つまり O(n) では計算できない O(n^2) の結果を意味します。

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

  • バッグをヒストグラムに変換します。

    hist = []
for c in B do:
    hist[c] = hist[c] + 1

  • 変更しようとしている実行中のヒストグラムを初期化します (histrunsum は histrun の文字の総数です)。

    histrun = []
histrunsum = 0

  • 2 つの操作が必要です。ヒストグラムに文字を追加し、削除します。それらは次のように動作します。

    add(c):
    if hist[c] > 0 and histrun[c] < hist[c] then:
        histrun[c] = histrun[c] + 1
        histrunsum = histrunsum + 1

remove(c):
    if histrun[c] > 0 then:
        histrun[c] = histrun[c] - 1
        histrunsum = histrunsum + 1

  • 基本的に、histrun は、現在の部分文字列の B に存在する文字数をキャプチャします。histrun が hist と等しい場合、サブストリングは B と同じ文字を持ちます。histrunsum が B の長さと等しい場合、histrun は hist と等しくなります。

  • ここで、最初の m 文字を histrun に追加します。histrunsum が B の長さと等しい場合。最初の部分文字列を出力します。ここで、文字列の最後に到達するまで、現在の部分文字列の最初の文字を削除し、次の文字を追加します。

  • hist と histrun は配列であるため、add、remove は O(1) です。hist が histrun と等しいかどうかのチェックは、histrunsum と length(B) を比較することによって行われるため、これも O(1) です。ループの反復回数は O(n) で、実行時間は O(n) です。

于 2011-11-05T20:33:21.343 に答える
1

答えてくれてありがとう。add()とメソッドはremove()、アルゴリズムが正しく機能するように変更する必要があります。

add(c):
    if hist[c] > 0 and histrun[c] < hist[c] then
        histrunsum++
    else
        histrunsum--

    histrun[c] = histrun[c] + 1


remove(c):
    if histrun[c] > hist[c] then
        histrunsum++
    else
        histrunsum--

    histrun[c] = histrun[c] - 1

説明: histrunsum は、両方のマルチセットがどの程度同一であるかのスコアと見なすことができます。

add(c): histrun マルチセットよりも histrun マルチセットの char の出現が少ない場合、histrun マルチセットが hist マルチセットに近づいているため、その char の追加の出現は「報われる」必要があります。histrun セットに少なくとも同等またはそれ以上の文字が既に存在し、追加の文字が負の場合。

remove(c): add(c) と同様に、char の削除が histrun マルチセット > hist マルチセットの数値である場合、正の重みが付けられます。

サンプルコード (PHP):

function multisetSubstrings($sequence, $mset)
{
    $multiSet = array();
    $substringLength = 0;
    foreach ($mset as $char)
    {
        $multiSet[$char]++;
        $substringLength++;
    }

    $sum = 0;
    $currentSet = array();
    $result = array();

    for ($i=0;$i<strlen($sequence);$i++)
    {

        if ($i>=$substringLength)
        {
            $c = $sequence[$i-$substringLength];

            if ($currentSet[$c] > $multiSet[$c])
                $sum++;
            else
                $sum--;

            $currentSet[$c]--;
        }


        $c = $sequence[$i];

        if ($currentSet[$c] < $multiSet[$c])
            $sum++;
        else
            $sum--;

        $currentSet[$c]++;

        echo $sum."<br>";


        if ($sum==$substringLength)
            $result[] = $i+1-$substringLength;
    }


    return $result;
}
于 2011-11-07T14:40:57.807 に答える
0

ハッシュを使用します。マルチセット内の各文字に対して、UNIQUE 素数を割り当てます。数値に関連付けられた素数をその数値の頻度と同じ回数掛けて、任意の文字列のハッシュを計算します。

例：CATTA。C = 2、A=3、T = 5 とする。ハッシュ = 2*3*5*5*3 = 450

マルチセットをハッシュします (文字列として扱います)。次に、入力文字列を調べて、長さ k の各部分文字列のハッシュを計算します (ここで、k は multiset 内の文字数です)。このハッシュがマルチセット ハッシュと一致するかどうかを確認します。はいの場合、それはそのような出来事の 1 つです。

ハッシュは、次のように線形時間で非常に簡単に計算できます。

multiset = { A, A, B, C }、A=2、B=3、C=5 とします。

マルチセット ハッシュ = 2*2*3*5 = 60

text = CABBAACCA とする

(i) CABB = 5*2*3*3 = 90

(ii) さて、次の文字は A で、破棄された文字は最初の文字 C です。したがって、新しいハッシュ = ( 90/5 )*2 = 36

(iii) ここで、A が破棄され、A も追加されるため、新しいハッシュ = ( 36/2 ) * 2= 36

(iv) ここで B が破棄され、C が追加されるため、ハッシュ = ( 36/3 ) * 5 = 60 = マルチセット ハッシュ。したがって、必要なオカレンスの 1 つ、BAAC が見つかりました。

この手順は明らかに O( n ) 時間かかります。

于 2012-08-16T07:15:45.567 に答える