最短繰り返しサブストリング[PYTHON]

Question

最短繰り返しサブストリングとその繰り返し回数を簡単に見つける方法はありますか？あなたがない場合は、実際の文字列を返す必要があります（最後のケース）。

>>> repeated('CTCTCTCTCTCTCTCTCTCTCTCT') 
('CT', 12) 

>>> repeated('GATCGATCGATCGATC')   
('GATC', 4) 

>>> repeated('GATCGATCGATCGATCG')   
('GATCGATCGATCGATCG', 1) 

何人かの人々は、それは私が私の努力を示すことができる「宿題」だと思うので：それは繰り返し部分文字列が一意の文字を持っていることを前提としているので

def repeated(sequentie): 
    string = '' 

    for i in sequentie: 
     if i not in string: 
      string += i 

    items = sequentie.count(string) 
    if items * len(string) == len(sequentie): 
     return (string, items) 
    else: 
     return (sequentie, 1) 

Answer 1

あなたの方法は、残念ながら、動作しません。これはそうではないかもしれません：

abaabaabaabaabaaba 

あなたはやや正しいトラックにいました。

def find_shorted_substring(s): 
    for i in range(1, len(s) + 1): 
     substring = s[:i] 
     repeats = len(s) // len(substring) 

     if substring * repeats == s: 
      return (substring, repeats) 

それは非常に効率的ではないが、それは動作します：私は考えることができる最短の方法はいくつかのプレフィックスが実際に文字列全体を構成している場合は何度も試してみてチェックすることです。それを行うより良い方法があります。