☰

Python で文字列が繰り返されるかどうかはどうすればわかりますか? 質問する

tag-icon • tag-icon python string pattern-matching
Python で文字列が繰り返されるかどうかはどうすればわかりますか? 質問する

特定の文字列が文字列全体で繰り返されるかどうかをテストする方法を探しています。

例:

[
    '0045662100456621004566210045662100456621',             # '00456621'
    '0072992700729927007299270072992700729927',             # '00729927'
    '001443001443001443001443001443001443001443',           # '001443'
    '037037037037037037037037037037037037037037037',        # '037'
    '047619047619047619047619047619047619047619',           # '047619'
    '002457002457002457002457002457002457002457',           # '002457'
    '001221001221001221001221001221001221001221',           # '001221'
    '001230012300123001230012300123001230012300123',        # '00123'
    '0013947001394700139470013947001394700139470013947',    # '0013947'
    '001001001001001001001001001001001001001001001001001',  # '001'
    '001406469760900140646976090014064697609',              # '0014064697609'
]

繰り返し文字列であり、

[
    '004608294930875576036866359447',
    '00469483568075117370892018779342723',
    '004739336492890995260663507109',
    '001508295625942684766214177978883861236802413273',
    '007518796992481203',
    '0071942446043165467625899280575539568345323741',
    '0434782608695652173913',
    '0344827586206896551724137931',
    '002481389578163771712158808933',
    '002932551319648093841642228739',
    '0035587188612099644128113879',
    '003484320557491289198606271777',
    '00115074798619102416570771',
]

これらはそうではない例です。

与えられた文字列の繰り返し部分は非常に長く、文字列自体も 500 文字以上になることがあります。そのため、各文字をループしてパターンを構築し、そのパターンを文字列の残りの部分と比較するのは、非常に遅いように思えます。これを数百の文字列に掛け合わせると、直感的な解決策は見つかりません。

正規表現について少し調べてみたところ、探しているものがわかっている場合、または少なくとも探しているパターンの長さがわかっている場合には正規表現が適しているようです。残念ながら、私はどちらも知りません。

文字列が繰り返されているかどうか、また繰り返されている場合、最も短い繰り返し部分列は何かをどのように判断すればよいでしょうか?

ベストアンサー1

正規表現と遅い Python 内ループを回避する簡潔な解決策を次に示します。

def principal_period(s):
    i = (s+s).find(s, 1, -1)
    return None if i == -1 else s[:i]

を参照してくださいコミュニティ Wiki の回答ベンチマーク結果のために@davidismが開始しました。要約すると、

David Zhang のソリューションは明らかな勝者であり、大規模な例セットでは他のすべてのソリューションよりも少なくとも 5 倍優れています。

(これは私の答えではなく、その答えの言葉です。)

これは、文字列が周期的であるのは、文字列自体の非自明な回転に等しい場合のみであるという観察に基づいています。 における の最初の出現のインデックスから主周期を復元できることに気付いた @AleksiTorhamosと、 Python の の(s+s)[1:-1]オプションの引数startとについて教えてくれた @AleksiTorhamo に感謝します。endstring.find

おすすめ記事