2

2日間、これについて調査しましたが、何も見つかりませんでした。そこで、独自の文字列繰り​​返し検出器を作成することにしました。基本的に機能

def findRepetitions (string):

文字列を受け取り、繰り返しを検索します。最も単純な形式に縮小された文字列のリストを返します。

サンプルの場合、次のようになります。

findRepetitions ("trololololo") --> ["olo"]
findRepetitions ("bookkeeper") ---> ["o", "k", "e"]
findRepetitions ("Hello, Molly") -> ["l", "l"]
findRepetitions ("abcdefgh") -----> []
findRepetitions ("102102102") ----> ["102"]

3番目の例では、関数は["ll"]ではなく["l"、 "l"]を返します。これは、隣接する文字でのみ繰り返しを検索するためです。

これは難しいかもしれませんが、私は文字通り長い間これについて考えていて、これに対する賢い解決策を見つけることができません。

4

2 に答える 2

3

これはよく知られている問題です。

http://en.wikipedia.org/wiki/Longest_repeated_substring_problem

この問題は効率的に解決できますが、トライを作成します。

http://en.wikipedia.org/wiki/Radix_tree

wikiページには、必要な唯一の関数であるノードのルックアップと追加の擬似コードと例が示されています。すべての文字から始まる文字列をトライに挿入します。たとえば、文字列abcdの場合は、abcd、bcd、cd、dを挿入します。トライのこの特定のインスタンスは、「サフィックスツリー」と呼ばれます。

http://en.wikipedia.org/wiki/Suffix_tree

すでに安定しているパスをトラバースするたびに、実際にはストリングの繰り返しを発見しています。これで、すべての繰り返しを個別のデータ構造にリストし、最長のものを抽出できます（必要な場合）。

于 2012-11-06T18:12:57.980 に答える
1

あなたの例は一貫していません。たとえば、l in 、in ;oloのように繰り返さないでください。インスタンス間にはあります。の連続した繰り返しは、、、、、およびです。「欲張り」アルゴリズムを求めていますか？だから、与えられた、それは戻るだろうか？Hello, Molly`trolololololtrolololololololoolololtrololololoolol

いずれにせよ、ここに少しのコードがあります。 

from collections import Counter

def find_repetition(p):
    """ Returns a lookup dictionary for repetitions. """ 
    lookup = Counter()
    while len(p) != 0:
        for i in xrange(len(p)):
            lookup[p[0:i]] += 1
        p = p[1:]
    return lookup

def repeats(p):
    a = find_repetition(p)
    rs = [i for i in a if a[i] > 1][1:]
    return [r for r in rs if r*2 in p]

私が説明したように「貪欲」にしたい場合は、一致するものが見つかったときに文字列を繰り返して切り刻む結果を取得する別の関数を追加する必要があります。

今のところ、結果は次のようになります。

test = "trololololo", "bookkeeper", "Hello, Molly", "abcdefgh", "102102102"

>>> for i in test:
>>>     repeats(i)

['lolo', 'lo', 'olol', 'ol']
['e', 'o', 'k']
['l']
[]
['210', '021', '102']

警告

find_repetition基本的に文字列のすべての長さの組み合わせを生成し、それらをCounterオブジェクトにスローするため、それほど速くはありません。

于 2012-11-06T19:02:13.600 に答える