Como posso saber se uma string se repete no Python?

352

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?

John
fonte
15
percorrer cada caractere tentando criar um padrão e, em seguida, verificar o padrão versus o restante da string parece muito lento - mas é?
Tim
2
possível duplicata de escrever um regex para detectar repetir-personagens
Avinash Raj
2
@AvinashRaj Isso corresponde apenas a parte de uma string, não a coisa completa.
John
11
@AvinashRaj O OP está perguntando sobre todas as soluções possíveis. A pergunta à qual você vincula aceita apenas a solução regex . Observe que o regex pode resolver o problema, mas em muito mais tempo do que o necessário. Por exemplo, uma solução ideal (isto é, tempo linear) usaria a árvore de sufixos do texto. Você só precisa encontrar a substring repetida mais longa e fazer algumas verificações nos comprimentos.
Bakuriu 7/04
2
@ TigerhawkT3 O conjunto de dados real é muito grande e difícil de manejar, mas os exemplos na pergunta fazem parte dele e, se você desejar, aqui está um pouco mais .
John John

Respostas:

570

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.

David Zhang
fonte
19
Você pode estender isso para encontrar a subsequência de repetição mais curta usando .find()ou em .index()vez de in, por exemplo. (s+s).find(s, 1, -1).
Aleksi Torhamo
11
Além disso, acho (s+s).find(s, 1, -1)que será (um pouco) mais rápido do que (s+s)[1:-1].find(s), pelo menos para seqüências maiores, já que o fatiamento significa que você precisa criar outra cópia (quase) de toda a sequência.
Aleksi Torhamo 08/04
13
É como se você pegasse uma onda sin ou cos de uma função periódica e a deslocasse para a direita. Como é totalmente periódico, as ondas acabam se combinando perfeitamente ... Os paralelos matemáticos com essa solução são fenomenais. :) Gostaria de poder dar-lhe + votos positivos.
Shashank
6
A recente atualização de Guido para o PEP 8 é relevante aqui: "Seja consistente nas declarações de retorno. Todas as declarações de retorno em uma função devem retornar uma expressão, ou nenhuma delas. Se qualquer declaração de retorno retornar uma expressão, qualquer declaração de retorno onde nenhum valor seja retornado deve declarar explicitamente isso como retorno Nenhum e uma declaração de retorno explícita deve estar presente no final da função (se possível). "
Zero Pireu
8
@WayneConrad Pegue uma corda, por exemplo, solte "abcd"o caractere à direita e coloque-o novamente à esquerda para obter "dabc". Esse procedimento é chamado de rotação de uma string para a direita por 1 caractere . Repita as nvezes para girar uma seqüência de caracteres para a direita n. Agora observe que, se tivermos uma sequência de kcaracteres, girar para a direita por qualquer múltiplo de kdeixa a sequência inalterada. Uma rotação não trivial de uma sequência é aquela cujo número de caractere não é um múltiplo do comprimento da sequência.
David Zhang
181

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.

Zero Pireu
fonte
6
Não tenho ideia de por que essa linha dupla concisa não é a resposta mais votada. As outras respostas não são ruins, mas esta é muito melhor. (Ele pode usar a expressão regular frequentemente denegrida , mas eu posso inspecionar isso muito mais facilmente do que as outras respostas muito mais longas, cheias de blocos aninhados, erros de digitação em potencial, erros pontuais etc.) Ah, bem, pior é melhor Eu suponho.
Paul Draper
9
Eu acho que existem duas razões principais para isso: 1) alguns programadores gostam mais de matemática do que gostam de expressões regulares e 2) já que variar o comprimento e a natureza das seqüências de entrada faz com que respostas diferentes avancem no desempenho, as sequências de caracteres de bordas super longas (que talvez nem apareçam nos dados reais) fazem com que essa solução pareça abaixo do ideal.
precisa saber é o seguinte
às vezes você encontra um grande preconceito em relação a expressões regulares. Tive dois gerentes que proibiram o uso de expressões regulares porque ouviram que expressões regulares são a ferramenta errada para o trabalho. Exceto offcourse, em seguida, eles passaram por me pedindo para implementar um motor regexp
joojaa
11
@PaulDraper: Adivinhe o que a regex está fazendo nos bastidores? ele está analisando a sequência e armazena cada elemento até que ocorra uma correspondência possível de repetição. É o mesmo que estado OP como muito lento. então, por ser um liner 2, não há ganho de desempenho.
Dhein
2
@Zaibis, eu normalmente concordo, mas essa é a solução mais curta e mais rápida ( stackoverflow.com/a/29482936/1212596).... exceto o de David, que foi publicado depois que eu fiz esse comentário. Na verdade, eu gosto mais da abordagem de David (inteligente!).
Paul Draper
90

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.

Shashank
fonte
3
Esta solução é incrível. Você pode alterar o método dos divisores para seguir o padrão de produção-consumidor. Para que produza os resultados à medida que são encontrados. Será uma pena se essa não for a resposta mais alta. Tudo o resto é força bruta.
precisa saber é o seguinte
3
@JustinDanielson Retorna um objeto gerador criado a partir de uma expressão gerador, que é um produtor implícito :) Ele avaliará preguiçosamente os divisores.
Shashank
11
Ohh Eu não sabia disso. Bem, melhor ainda. : Entenda por que você deseja evitar o sqrt, mas você pode usar n / 2 como o limite superior do intervalo do divisor.
JustinDanielson
11
@JustinDanielson Obrigado pela sugestão, o limite superior do intervalo agora é (n/2)inclusivo.
Shashank #
11
Deve n / 2em divisors()ser n // 2?
precisa saber é o seguinte
87

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 1 gráfico


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 1 gráfico


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

Gráfico Corpus 3


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

davidism
fonte
37

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
TigerhawkT3
fonte
Não é uma solução de força bruta?
JustinDanielson
7
@JustinDanielson Sim. Mas uma solução, no entanto.
Sinkingpoint
3
Estou vendo cerca de 1e-5 a 3e-5 segundos para sequências curtas, 3e-5 a 4e-5 segundos para sequências longas bem-sucedidas (1000 caracteres) e um pouco menos de um milissegundo para sequências longas sem êxito (pior caso) . Assim, mil seqüências de 1.000 caracteres levariam cerca de um segundo. Comparado com a resposta matemática, ele encontra correspondências 10 vezes mais rápidas, mas leva três vezes mais para falhar.
precisa saber é o seguinte
repeat('aa')retornaNone
Tom Cornebize
2
len(string[0:i])é sempre igual a i(neste caso, pelo menos). Substituí-los e também salvar len(string)e string[0:i]variáveis ​​pode acelerar as coisas. Também IMO isso é uma grande solução, impressionante;)
ThatWeirdo
24

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.

davidism
fonte
16

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
RiaD
fonte
Seu prefix_function()não é Python válida: você tem que faltam dois pontos em seus whilee ifdeclarações, e &&em vez de and. Depois de consertá-los, ele falha por UnboundLocalError: local variable 'i' referenced before assignmentcausa da linha for i in range(i, n):.
Zero Pireu
Obrigado :-) Se você pode montar uma função que usa o seu prefix_function()para retornar resultados semelhantes às outras respostas - a substring mais curta ou None- eu a incluirei em uma referência revisada que estou montando.
Zero Pireu
@ZeroPiraeus, Ele funciona muito bem, na verdade, eu só chamou-o de uma maneira errada
Riad
16

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.

Antti Haapala
fonte
Essa solução é praticamente idêntica à minha otimizada. Vejo que você tem um rangelimite de length//2, exatamente como eu tive - você deve mudar isso para length//2+1se quiser pegar as cordas que são exatamente duplicadas (por exemplo 'aabaab').
precisa saber é o seguinte
E agora eles são idênticos! \ o / Preciso prestar mais atenção à otimização no futuro, mas estou feliz que o algoritmo em si esteja correto.
precisa saber é o seguinte
15

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"
Saksham Varma
fonte
Agora que olho para este com cuidado, parece quase idêntico à minha solução originalmente postada (antes de qualquer edição), com as únicas diferenças sendo o comprimento e a substring. Eu acho que tinha um bom algoritmo. : P
TigerhawkT3
@ TigerhawkT3 Sim, de fato! :)
Saksham Varma
9

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.

Cavaleiro Lógico
fonte
Nada mal :-) O benchmark é executado no Python 3.4 (em parte porque o OP não especifica uma versão e é isso que todos deveriam estar usando, e em parte porque usa o novo statisticsmódulo), então tive que alterar seus /s para //s e substitua xrange()por range()(que se comporta como 2.x xrange()em 3.x).
Zero Pireu
Aqui estão as revisões do benchmark, para que você possa revisar minhas alterações, a propósito.
Zero Pireu
Obrigado Zero. Isso foi rápido. Os resultados foram um pouco abaixo das minhas previsões. Suspeito que as técnicas que usei para velocidade no Python 2.7 não sejam muito eficazes no Python 3.4. Oh, bem - um exercício divertido e educacional.
Logic Knight
//em 3.x é divisão inteira (assim como o comportamento 2.x de /), enquanto 3.x /é divisão flutuante (que eu tenho certeza que seria muito mais lenta, mesmo que não quebre sua solução, causando uma tentativa de usar um flutuador como um índice). Como mencionado, 3.x range()é a mesma coisa que 2.x xrange(); não existe equivalente a 2.x range()no 3.x. Portanto, não acho que essa seja a causa de qualquer discrepância entre o benchmark e os tempos que você fez. Provavelmente, o 3.x é mais lento do que o 2.x (ou talvez sua máquina seja mais rápida que a minha).
Zero Pireu
Quando eu chegar em algum tempo, poderei ter um olhar mais atento sobre as diferenças de tempo de execução entre Python 2 e Python 3.
Logic Cavaleiro
2

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'
Piotr Dabkowski
fonte
Obrigado :) Mas não otimizei muito. Eu só queria apresentar uma abordagem diferente, porque outras respostas estão focadas em encontrar o padrão e minha abordagem se concentra em provar que não há padrão :) Portanto, para seqüências aleatórias, meu algoritmo deve correr muito mais rápido.
Piotr Dabkowski
0

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'
sachinruk
fonte
-1

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'

Srivishnu
fonte