1

0 と 1 の文字列があります。すぐに繰り返される部分文字列として「contiguous-double」を定義します。たとえば、文字列 "011101010101110" は "011 1010 1010 1110" に分割でき、"011(1010)1110" に圧縮できます。

文字列内のすべての連続する double を見つけるための良いアルゴリズムはありますか? 私が思いつくことができる最高のものは、文字列の長さに関して二次です：

def all_contiguous_doubles(s):
    for j in range(len(s)):
        for i in range(j):
            if s[i:j] == s[j:2*j - i]:
                print "%s(%s)%s" % (s[:i], s[i:j], s[2*j - i:])
4

3 に答える 3

1

ここでは、O(n^2) の時間の複雑さとO(n^2)の空間の複雑さを持つ動的プログラミング ソリューションを紹介します。ここで、n は元の文字列の長さです。

以下では、関数 dl(r,c) を再帰的に定義します。dl(r,c) を表にして正しい順序で埋めれば O(n^2) で完成します。

定義:

char(i) = 位置 i の文字

substr(i) = 位置 i から元の文字列の末尾に向かって始まる部分文字列。

dl(r,c) = substr(r) と substr(c) の共通の重複しないプレフィックスの長さ。

dl(r,c) の再帰的定義:

dl(r,c) は対称であるため、r <= c のみを考慮します。

r == c の場合、dl(r,c) = 0。部分文字列が同じポイントから始まる場合、常に重複するためです。

char(r) != char(c) の場合、dl(r,c) = 0。プレフィックスが同じではないためです。

if char(r) == char(c),
    if dl(r+1,c+1) + 1 < c-r
        dl(r,c) = dl(r+1,c+1) + 1
    else
        dl(r,c) = dl(r+1,c+1)

の最大値dl(r,c)がdl(r,c) == c-rあなたの答えになります。

于 2012-11-20T02:20:48.187 に答える
0

正規表現の jan メンションを使用します/(.+)$1/

これは、おそらくそうでなければ機能する単純なアルゴリズムです。

関数を作成する

get_largest(string, i, j)

i と j の間の最大の double を返します。

min(20, (ji)//2) の hash_size を使用します

ここで、hash_size が 20 であるとします。長さ 20 の最も頻度の低い部分文字列と、それが発生するすべての位置を見つけます。(これは、ハッシュ テーブルを使用してすばやく実行できます)

見つかった位置が [10, 110, 320, 500, ..] であるとしましょう。string[10:110]、string[110, 320]、string[320, 500] などを見てください。これらの部分文字列は複数回発生し、これらの部分文字列のすべての位置を見つけて、上記の手法またはその修正版を使用して double を確認します。

長さ 20 の最も頻度の低い部分文字列を含む double が見つからない場合は、再帰的に分割して征服し、最も頻度の低い部分文字列を含まないすべての最長の部分文字列を検索できます。

うまくいけば、ほとんどの場合、これは高速になるはずです。

于 2012-11-20T01:12:42.777 に答える
0

圧縮が本当に最終的な目標である場合:

文字列「0000」「0001」、「1010」などをそれぞれの16進数「0-F」にマッピングするサイズ16のルックアップテーブルを用意しないのはなぜですか?

表現を保存する場合: バイナリ文字列を一連の 16 進数文字列に変換しますか?

また、 Gray Codeを検索することもできます。ここで、バイナリ シーケンスでは、前の数値と現在の数値が正確に 1 ビット異なります。

テーブルに 0 ～ F のグレイ コード表現がある場合、次のようになります。

16 進文字列の文字の場合: 前または現在の文字が「グレイ コード」順で対応する文字かどうかを確認します。その場合は、さらに圧縮できます。(異なるビットが真ん中にある可能性もあります-いくつかのケースは適切に処理する必要があります' )

于 2012-11-20T06:39:32.453 に答える