40

シーケンスを 3 回以上繰り返さなければならないという警告を使用して、文字列内で最も長いシーケンスを見つける必要があります。たとえば、私の文字列が次の場合：

fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld

次に、値「helloworld」が返されるようにします。

これを達成するいくつかの方法を知っていますが、私が直面している問題は、実際の文字列がとてつもなく大きいことです。そのため、タイムリーに実行できる方法を本当に探しています。

4

6 に答える 6

33

この問題は、最も長く繰り返される部分文字列問題の変形であり、接尾辞木を使用してそれを解決するためのO（n）時間アルゴリズムがあります。（Wikipediaで提案されているように）アイデアは、接尾辞ツリーを構築し（time O（n））、ツリー内のすべてのノードに子孫の数で注釈を付け（DFSを使用してtime O（n））、次に少なくとも3つの子孫を持つツリーの最も深いノード（DFSを使用した時間O（n））。この全体的なアルゴリズムには時間O（n）がかかります。

とは言うものの、接尾辞木は構築が難しいことで有名なので、この実装を試みる前に、接尾辞木を実装するPythonライブラリを見つけたいと思うでしょう。Googleですばやく検索すると、このライブラリが見つかりますが、これが適切な実装であるかどうかはわかりません。

別のオプションは、 LCP配列と組み合わせて接尾辞配列を使用することです。LCP配列内の隣接する要素のペアを反復処理し、各ペアの最小値を取得して、この方法で見つけた最大数を格納できます。これは、少なくとも3回繰り返される最長の文字列の長さに対応し、そこから文字列自体を読み取ることができます。

接尾辞配列を構築するためのいくつかの単純なアルゴリズムがあり（Manber-Myersアルゴリズムは時間O（n log n）で実行され、コーディングするのはそれほど難しくありません）、葛西のアルゴリズムは時間O（n）でLCP配列を構築し、かなりですコードを作成するのは簡単です。

お役に立てれば！

于 2012-06-18T20:17:32.607 に答える
12

defaultdict を使用して、入力文字列の各位置から始まる各部分文字列を集計します。重複する一致を含める必要があるかどうかは、OP では明確ではありませんでした。このブルート フォース メソッドにはそれらが含まれます。

from collections import defaultdict

def getsubs(loc, s):
    substr = s[loc:]
    i = -1
    while(substr):
        yield substr
        substr = s[loc:i]
        i -= 1

def longestRepetitiveSubstring(r, minocc=3):
    occ = defaultdict(int)
    # tally all occurrences of all substrings
    for i in range(len(r)):
        for sub in getsubs(i,r):
            occ[sub] += 1

    # filter out all substrings with fewer than minocc occurrences
    occ_minocc = [k for k,v in occ.items() if v >= minocc]

    if occ_minocc:
        maxkey =  max(occ_minocc, key=len)
        return maxkey, occ[maxkey]
    else:
        raise ValueError("no repetitions of any substring of '%s' with %d or more occurrences" % (r,minocc))

プリント:

('helloworld', 3)
于 2012-06-18T21:36:26.187 に答える
4

最後から始めて、頻度を数えて、最も多い要素が3回以上現れたら止めましょう。

from collections import Counter
a='fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld'
times=3
for n in range(1,len(a)/times+1)[::-1]:
    substrings=[a[i:i+n] for i in range(len(a)-n+1)]
    freqs=Counter(substrings)
    if freqs.most_common(1)[0][1]>=3:
        seq=freqs.most_common(1)[0][0]
        break
print "sequence '%s' of length %s occurs %s or more times"%(seq,n,times)

結果： 

>>> sequence 'helloworld' of length 10 occurs 3 or more times

編集：ランダムな入力を扱っていて、共通の部分文字列の長さが短いと感じている場合は、（速度が必要な場合は）小さな部分文字列から始めて、少なくとも 3 回:

from collections import Counter
a='fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld'
times=3
for n in range(1,len(a)/times+1):
    substrings=[a[i:i+n] for i in range(len(a)-n+1)]
    freqs=Counter(substrings)
    if freqs.most_common(1)[0][1]<3:
        n-=1
        break
    else:
        seq=freqs.most_common(1)[0][0]
print "sequence '%s' of length %s occurs %s or more times"%(seq,n,times)

上記と同じ結果です。

于 2012-06-18T21:31:20.023 に答える
1

頭に浮かんだ最初のアイデアは、徐々に大きくなる正規表現で検索することです。

import re

text = 'fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld'
largest = ''
i = 1

while 1:
    m = re.search("(" + ("\w" * i) + ").*\\1.*\\1", text)
    if not m:
        break
    largest = m.group(1)
    i += 1

print largest    # helloworld

コードは正常に実行されました。時間計算量は少なくとも O(n^2) のようです。

于 2012-06-18T21:11:59.793 に答える
0

入力文字列を逆にすると、次のような正規表現にフィードされ(.+)(?:.*\1){2}
ます。これにより、最長の文字列が3回繰り返されます。（答えは逆キャプチャグループ1）

編集：
私はこの方法でキャンセルと言わなければなりません。それは最初の一致に依存します。これまでのところ、現在の長さと最大の長さに対してテストされていない限り、反復ループでは、正規表現はこれに対して機能しません。

于 2012-06-18T22:00:55.283 に答える