Bir yol ya da belirli bir dize tüm dize için tekerrür olup olmadığını test etmek için arıyorum.

Örnekler:

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

kendilerini tekrar eden dizeler vardır, ve

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

yok olanların örnekleri.

Yinelenen bölümler dizeleri ben vermiş olabilir oldukça uzun ve dizeleri kendilerini olabilir 500 veya daha fazla karakter, yani döngü her karakter inşa etmeye örüntüyü kontrol desen vs gerisini dizesi gibi korkunç yavaş. Potansiyel tarafından dizeler ve ben yüzlerce herhangi bir sezgisel çözüm göremiyorum çarpın.

Yukarıdaki diyagram içine biraz baktım ve sizin için ne arıyorsanız, ya da en azından aradığınız desen uzunluğunu biliyorum iyi görünüyorlar. Ne yazık ki, ne biliyorum.

Nasıl olur, en kısa yinelenen subsequence ne varsa bir dize kendini tekrar ediyorsa ve söyleyebilir miyim?

İşte düzenli ifadeler ve yavaş bir şekilde Python döngüler: önler kısa bir çözüm

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

Community Wiki answer @deney sonuçları için davidism tarafından başlatılmış bakın. Özet

David Zhang çözümü kesin kazanan, büyük bir örnek kümesi için en az 5 kat diğer iyi performans.

(Cevap kelimeleri, benim değil.)

Bu bir dize periyodik eğer kendisi saçma bir rotasyon eşit ise, yalnızca ve olduğu gözlemine dayanmaktadır. Tebrikler @AleksiTorhamo için gerçekleştirmek için elimizden gelen sonra kurtarmak Müdür dönemde dizinin ilk geçtiği s (s s)[1:-1] ve bilgilendirme için benim isteğe bağlı start end bağımsız değişkenler Python string.find.