Como posso saber se uma string se repete no Python?

Estou procurando uma maneira de testar se uma determinada string se repete ou não para a string inteira.

Exemplos:

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

são cordas que se repetem, e

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

são exemplos daqueles que não o fazem.

As seções repetidas das strings que me são dadas podem ser bastante longas, e as strings em si podem ter 500 ou mais caracteres, então percorrer cada caractere tentando criar um padrão e verificar o padrão versus o restante da string parece muito lento. Multiplique isso por potencialmente centenas de strings e não vejo nenhuma solução intuitiva.

Analisei um pouco as regexes e elas parecem boas quando você sabe o que está procurando ou pelo menos a duração do padrão que está procurando. Infelizmente, eu também não conheço.

Como posso saber se uma sequência está se repetindo e se for, qual é a subsequência de repetição mais curta?

Aqui está uma solução concisa que evita expressões regulares e loops in-Python lentos:

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

Veja a resposta do Community Wiki iniciada por @davidism para obter resultados de benchmark. Em suma,

A solução de David Zhang é a vencedora, superando todas as outras em pelo menos 5x no grande conjunto de exemplos.

(Palavras dessa resposta, não minhas.)

Isso se baseia na observação de que uma string é periódica se, e somente se, é igual a uma rotação não trivial de si mesma. Parabéns a @AleksiTorhamo por perceber que podemos recuperar o período principal do índice da primeira ocorrência de sin (s+s)[1:-1]e por me informar sobre os argumentos starte endargumentos opcionais do Python string.find.

Aqui está uma solução usando expressões regulares.

import re

REPEATER = re.compile(r"(.+?)\1+$")

def repeated(s):
    match = REPEATER.match(s)
    return match.group(1) if match else None

Iterando sobre os exemplos na pergunta:

examples = [
    '0045662100456621004566210045662100456621',
    '0072992700729927007299270072992700729927',
    '001443001443001443001443001443001443001443',
    '037037037037037037037037037037037037037037037',
    '047619047619047619047619047619047619047619',
    '002457002457002457002457002457002457002457',
    '001221001221001221001221001221001221001221',
    '001230012300123001230012300123001230012300123',
    '0013947001394700139470013947001394700139470013947',
    '001001001001001001001001001001001001001001001001001',
    '001406469760900140646976090014064697609',
    '004608294930875576036866359447',
    '00469483568075117370892018779342723',
    '004739336492890995260663507109',
    '001508295625942684766214177978883861236802413273',
    '007518796992481203',
    '0071942446043165467625899280575539568345323741',
    '0434782608695652173913',
    '0344827586206896551724137931',
    '002481389578163771712158808933',
    '002932551319648093841642228739',
    '0035587188612099644128113879',
    '003484320557491289198606271777',
    '00115074798619102416570771',
]

for e in examples:
    sub = repeated(e)
    if sub:
        print("%r: %r" % (e, sub))
    else:
        print("%r does not repeat." % e)

... produz esta saída:

'0045662100456621004566210045662100456621': '00456621'
'0072992700729927007299270072992700729927': '00729927'
'001443001443001443001443001443001443001443': '001443'
'037037037037037037037037037037037037037037037': '037'
'047619047619047619047619047619047619047619': '047619'
'002457002457002457002457002457002457002457': '002457'
'001221001221001221001221001221001221001221': '001221'
'001230012300123001230012300123001230012300123': '00123'
'0013947001394700139470013947001394700139470013947': '0013947'
'001001001001001001001001001001001001001001001001001': '001'
'001406469760900140646976090014064697609': '0014064697609'
'004608294930875576036866359447' does not repeat.
'00469483568075117370892018779342723' does not repeat.
'004739336492890995260663507109' does not repeat.
'001508295625942684766214177978883861236802413273' does not repeat.
'007518796992481203' does not repeat.
'0071942446043165467625899280575539568345323741' does not repeat.
'0434782608695652173913' does not repeat.
'0344827586206896551724137931' does not repeat.
'002481389578163771712158808933' does not repeat.
'002932551319648093841642228739' does not repeat.
'0035587188612099644128113879' does not repeat.
'003484320557491289198606271777' does not repeat.
'00115074798619102416570771' does not repeat.

A expressão regular (.+?)\1+$é dividida em três partes:

1. (.+?)é um grupo correspondente que contém pelo menos um (mas o mínimo possível) de qualquer caractere (porque +?não é ganancioso ).

2. \1+ verifica pelo menos uma repetição do grupo correspondente na primeira parte.

3. $verifica o final da sequência para garantir que não haja conteúdo extra e não repetitivo após as substrings repetidas (e usar re.match()garante que não haja texto não repetitivo antes das substrings repetidas).

No Python 3.4 e posterior, você pode largar o $e usar re.fullmatch(), ou (em qualquer Python, pelo menos, já em 2.3), seguir o outro caminho e usar re.search()com o regex ^(.+?)\1+$, que são mais de gosto pessoal do que qualquer outra coisa.

Você pode observar que, para que uma sequência seja considerada repetida, seu comprimento deve ser divisível pelo comprimento de sua sequência repetida. Dado que, aqui está uma solução que gera divisores de comprimento a partir 1de n / 2inclusiva, divide a string original em substrings com o comprimento dos divisores, e testa a igualdade do conjunto de resultados:

from math import sqrt, floor

def divquot(n):
    if n > 1:
        yield 1, n
    swapped = []
    for d in range(2, int(floor(sqrt(n))) + 1):
        q, r = divmod(n, d)
        if r == 0:
            yield d, q
            swapped.append((q, d))
    while swapped:
        yield swapped.pop()

def repeats(s):
    n = len(s)
    for d, q in divquot(n):
        sl = s[0:d]
        if sl * q == s:
            return sl
    return None

EDIT: No Python 3, o /operador mudou para fazer a divisão de flutuação por padrão. Para obter a intdivisão do Python 2, você pode usar o //operador. Obrigado a @ TigerhawkT3 por trazer isso à minha atenção.

O //operador executa a divisão inteira no Python 2 e Python 3, por isso atualizei a resposta para suportar as duas versões. A parte em que testamos para ver se todas as substrings são iguais agora é uma operação de curto-circuito usando alle uma expressão geradora.

ATUALIZAÇÃO: em resposta a uma alteração na pergunta original, o código agora foi atualizado para retornar a menor substring de repetição, se existir e Nonese não existir . A @godlygeek sugeriu o uso divmodpara reduzir o número de iterações no divisorsgerador, e o código foi atualizado para corresponder a isso também. Agora ele retorna todos os divisores positivos de nem ordem crescente, exclusivos de nsi mesmos.

Atualização adicional para alto desempenho: Após vários testes, cheguei à conclusão de que simplesmente testar a igualdade de cadeias tem o melhor desempenho de qualquer solução de fatiamento ou iterador no Python. Portanto, peguei uma folha do livro de @ TigerhawkT3 e atualizei minha solução. Agora é 6x mais rápido do que antes, notavelmente mais rápido que a solução da Tigerhawk, mas mais lento que a de David.

Aqui estão alguns parâmetros de referência para as várias respostas a esta pergunta. Houve alguns resultados surpreendentes, incluindo um desempenho totalmente diferente, dependendo da string sendo testada.

Algumas funções foram modificadas para funcionar com o Python 3 (principalmente substituindo /por //para garantir a divisão inteira). Se você vir algo errado, deseja adicionar sua função ou adicionar outra sequência de teste, execute ping em @ZeroPiraeus na sala de chat do Python .

Em resumo: há uma diferença de 50x entre as soluções com melhor e pior desempenho para o grande conjunto de dados de exemplo fornecidos pelo OP aqui (através deste comentário). A solução de David Zhang é a vencedora, superando todas as outras em cerca de 5x no grande conjunto de exemplos.

Algumas das respostas são muito lentas em casos extremamente grandes "sem correspondência". Caso contrário, as funções parecem ter vencedores igualmente iguais ou claros, dependendo do teste.

Aqui estão os resultados, incluindo gráficos feitos com matplotlib e seaborn para mostrar as diferentes distribuições:

Corpus 1 (exemplos fornecidos - conjunto pequeno)

mean performance:
 0.0003  david_zhang
 0.0009  zero
 0.0013  antti
 0.0013  tigerhawk_2
 0.0015  carpetpython
 0.0029  tigerhawk_1
 0.0031  davidism
 0.0035  saksham
 0.0046  shashank
 0.0052  riad
 0.0056  piotr

median performance:
 0.0003  david_zhang
 0.0008  zero
 0.0013  antti
 0.0013  tigerhawk_2
 0.0014  carpetpython
 0.0027  tigerhawk_1
 0.0031  davidism
 0.0038  saksham
 0.0044  shashank
 0.0054  riad
 0.0058  piotr

Corpus 2 (exemplos fornecidos - conjunto grande)

mean performance:
 0.0006  david_zhang
 0.0036  tigerhawk_2
 0.0036  antti
 0.0037  zero
 0.0039  carpetpython
 0.0052  shashank
 0.0056  piotr
 0.0066  davidism
 0.0120  tigerhawk_1
 0.0177  riad
 0.0283  saksham

median performance:
 0.0004  david_zhang
 0.0018  zero
 0.0022  tigerhawk_2
 0.0022  antti
 0.0024  carpetpython
 0.0043  davidism
 0.0049  shashank
 0.0055  piotr
 0.0061  tigerhawk_1
 0.0077  riad
 0.0109  saksham

Corpus 3 (casos extremos)

mean performance:
 0.0123  shashank
 0.0375  david_zhang
 0.0376  piotr
 0.0394  carpetpython
 0.0479  antti
 0.0488  tigerhawk_2
 0.2269  tigerhawk_1
 0.2336  davidism
 0.7239  saksham
 3.6265  zero
 6.0111  riad

median performance:
 0.0107  tigerhawk_2
 0.0108  antti
 0.0109  carpetpython
 0.0135  david_zhang
 0.0137  tigerhawk_1
 0.0150  shashank
 0.0229  saksham
 0.0255  piotr
 0.0721  davidism
 0.1080  zero
 1.8539  riad

Os testes e resultados brutos estão disponíveis aqui .

Solução não regex:

def repeat(string):
    for i in range(1, len(string)//2+1):
        if not len(string)%len(string[0:i]) and string[0:i]*(len(string)//len(string[0:i])) == string:
            return string[0:i]

Solução não-regex mais rápida, graças a @ThatWeirdo (veja comentários):

def repeat(string):
    l = len(string)
    for i in range(1, len(string)//2+1):
        if l%i: continue
        s = string[0:i]
        if s*(l//i) == string:
            return s

A solução acima raramente é mais lenta que a original em alguns por cento, mas geralmente é um pouco mais rápida - às vezes muito mais rápida. Ainda não é mais rápido que o davidism para strings mais longos, e a solução regex do zero é superior para strings curtos. Ele é o mais rápido (de acordo com o teste do davidism no github - veja a resposta dele) com seqüências de caracteres de 1000 a 1500 caracteres. Independentemente disso, é confiavelmente o segundo mais rápido (ou melhor) em todos os casos que testei. Obrigado, ThatWeirdo.

Teste:

print(repeat('009009009'))
print(repeat('254725472547'))
print(repeat('abcdeabcdeabcdeabcde'))
print(repeat('abcdefg'))
print(repeat('09099099909999'))
print(repeat('02589675192'))

Resultados:

009
2547
abcde
None
None
None

Primeiro, corte pela metade a corda, contanto que seja uma duplicata em "2 partes". Isso reduz o espaço de pesquisa se houver um número par de repetições. Em seguida, trabalhando para a frente para encontrar a menor sequência repetida, verifique se a divisão da sequência completa por sub-sequência cada vez maior resulta apenas em valores vazios. Apenas sub-strings length // 2precisam ser testadas, pois qualquer coisa acima disso não teria repetições.

def shortest_repeat(orig_value):
    if not orig_value:
        return None

    value = orig_value

    while True:
        len_half = len(value) // 2
        first_half = value[:len_half]

        if first_half != value[len_half:]:
            break

        value = first_half

    len_value = len(value)
    split = value.split

    for i in (i for i in range(1, len_value // 2) if len_value % i == 0):
        if not any(split(value[:i])):
            return value[:i]

    return value if value != orig_value else None

Isso retorna a correspondência mais curta ou Nenhuma, se não houver correspondência.

O problema também pode ser resolvido O(n)na pior das hipóteses com a função prefixo.

Observe que, em geral, pode ser mais lento (UPD: e muito mais lento) do que outras soluções que dependem do número de divisores de n, mas geralmente encontram falhas mais cedo, acho que um dos casos ruins para eles será aaa....aab, onde existemn - 1 = 2 * 3 * 5 * 7 ... *p_n - 1 a 's

Antes de tudo, você precisa calcular a função de prefixo

def prefix_function(s):
    n = len(s)
    pi = [0] * n
    for i in xrange(1, n):
        j = pi[i - 1]
        while(j > 0 and s[i] != s[j]):
            j = pi[j - 1]
        if (s[i] == s[j]):
            j += 1
        pi[i] = j;
    return pi

então, ou não há resposta ou o menor período é

k = len(s) - prefix_function(s[-1])

e você só precisa verificar se k != n and n % k == 0(se a k != n and n % k == 0resposta fors[:k] sim, então não há resposta

Você pode verificar a prova aqui (em russo, mas o tradutor on-line provavelmente fará o truque)

def riad(s):
    n = len(s)
    pi = [0] * n
    for i in xrange(1, n):
        j = pi[i - 1]
        while(j > 0 and s[i] != s[j]):
            j = pi[j - 1]
        if (s[i] == s[j]):
            j += 1
        pi[i] = j;
    k = n - pi[-1]
    return s[:k] if (n != k and n % k == 0) else None

Esta versão tenta apenas os comprimentos de sequência candidatos que são fatores do comprimento da sequência; e usa o *operador para criar uma sequência completa a partir da sequência candidata:

def get_shortest_repeat(string):
    length = len(string)
    for i in range(1, length // 2 + 1):
        if length % i:  # skip non-factors early
            continue

        candidate = string[:i]
        if string == candidate * (length // i):
            return candidate

    return None

Agradecemos a TigerhawkT3 por perceber que, length // 2sem, + 1isso não corresponderia ao ababcaso.

Aqui está uma solução direta, sem regexes.

Para substrings de spartida do índice zeroth, de comprimentos 1 alen(s) , verifique se essa substring substré o padrão repetido. Essa verificação pode ser realizada concatenando substr-se os ratiotempos, de modo que o comprimento da cadeia assim formada seja igual ao comprimento de s. Por isso ratio=len(s)/len(substr).

Retornar quando a primeira substring for encontrada. Isso forneceria a menor substring possível, se houver.

def check_repeat(s):
    for i in range(1, len(s)):
        substr = s[:i]
        ratio = len(s)/len(substr)
        if substr * ratio == s:
            print 'Repeating on "%s"' % substr
            return
    print 'Non repeating'

>>> check_repeat('254725472547')
Repeating on "2547"
>>> check_repeat('abcdeabcdeabcdeabcde')
Repeating on "abcde"

Comecei com mais de oito soluções para esse problema. Alguns eram baseados em regex (match, findall, split), outros em fatiamento e teste de strings e outros com métodos de strings (find, count, split). Cada um tinha benefícios em termos de clareza, tamanho, velocidade e consumo de memória. Eu ia postar minha resposta aqui quando percebi que a velocidade de execução era classificada como importante, então fiz mais testes e melhorias para chegar a isso:

def repeating(s):
    size = len(s)
    incr = size % 2 + 1
    for n in xrange(1, size//2+1, incr):
        if size % n == 0:
            if s[:n] * (size//n) == s:
                return s[:n]

Esta resposta parece semelhante a algumas outras respostas aqui, mas possui algumas otimizações de velocidade que outros não usaram:

• xrange é um pouco mais rápido nesta aplicação,
• se uma sequência de entrada tiver um comprimento ímpar, não verifique substrings de comprimento par,
• usando s[:n]diretamente, evitamos criar uma variável em cada loop.

Eu estaria interessado em ver como isso funciona nos testes padrão com hardware comum. Acredito que será muito aquém do excelente algoritmo de David Zhang na maioria dos testes, mas, caso contrário, deve ser bastante rápido.

Eu achei esse problema muito contra-intuitivo. As soluções que pensei que seriam rápidas eram lentas. As soluções que pareciam lentas eram rápidas! Parece que a criação de strings do Python com o operador multiply e as comparações de strings são altamente otimizadas.

Essa função é executada muito rapidamente (testada e é três vezes mais rápida que a solução mais rápida aqui em strings com mais de 100k caracteres e a diferença fica maior quanto mais tempo o padrão de repetição). Ele tenta minimizar o número de comparações necessárias para obter a resposta:

def repeats(string):
    n = len(string)
    tried = set([])
    best = None
    nums = [i for i in  xrange(2, int(n**0.5) + 1) if n % i == 0]
    nums = [n/i for i in nums if n/i!=i] + list(reversed(nums)) + [1]
    for s in nums:
        if all(t%s for t in tried):
            print 'Trying repeating string of length:', s
            if string[:s]*(n/s)==string:
                best = s
            else:
                tried.add(s)
    if best:
        return string[:best]

Observe que, por exemplo, para a sequência de comprimento 8, ele verifica apenas fragmentos de tamanho 4 e não precisa mais testar porque o padrão de comprimento 1 ou 2 resultaria na repetição do padrão de comprimento 4:

>>> repeats('12345678')
Trying repeating string of length: 4
None

# for this one we need only 2 checks 
>>> repeats('1234567812345678')
Trying repeating string of length: 8
Trying repeating string of length: 4
'12345678'

Na resposta de David Zhang, se temos algum tipo de buffer circular Isso não vai funcionar: principal_period('6210045662100456621004566210045662100456621')devido à partida 621, onde eu teria gostado para cuspir: 00456621.

Estendendo sua solução, podemos usar o seguinte:

def principal_period(s):
    for j in range(int(len(s)/2)):
        idx = (s[j:]+s[j:]).find(s[j:], 1, -1)
        if idx != -1:
            # Make sure that the first substring is part of pattern
            if s[:j] == s[j:][:idx][-j:]:
                break

    return None if idx == -1 else s[j:][:idx]

principal_period('6210045662100456621004566210045662100456621')
>>> '00456621'

Aqui está o código em python que verifica a repetição da sub string na string principal fornecida pelo usuário .

print "Enter a string...."
#mainstring = String given by user
mainstring=raw_input(">")
if(mainstring==''):
    print "Invalid string"
    exit()
#charlist = Character list of mainstring
charlist=list(mainstring)
strarr=''
print "Length of your string :",len(mainstring)
for i in range(0,len(mainstring)):
    strarr=strarr+charlist[i]
    splitlist=mainstring.split(strarr)
    count = 0
    for j in splitlist:
        if j =='':
            count+=1
    if count == len(splitlist):
        break
if count == len(splitlist):
    if count == 2:
        print "No repeating Sub-String found in string %r"%(mainstring)

    else:
        print "Sub-String %r repeats in string %r"%(strarr,mainstring)
else :
    print "No repeating Sub-String found in string %r"%(mainstring)

Entrada :

0045662100456621004566210045662100456621

Saída :

Comprimento da sua corda: 40

A sub-string '00456621' se repete na string '0045662100456621004566210045662100456621'

Entrada :

004608294930875576036866359447

Saída :

Comprimento da sua corda: 30

Nenhuma Sub-String repetida encontrada na string '004608294930875576036866359447'