¿Cómo puedo saber si una cadena se repite en Python?

Estoy buscando una manera de probar si una cadena dada se repite o no para toda la cadena o no.

Ejemplos:

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

son cadenas que se repiten, y

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

son ejemplos de los que no.

Las secciones repetidas de las cadenas que me dan pueden ser bastante largas, y las cadenas en sí pueden tener 500 o más caracteres, por lo que recorrer cada personaje tratando de construir un patrón y luego verificar el patrón frente al resto de la cadena parece muy lento. Multiplique eso por potencialmente cientos de cadenas y no puedo ver ninguna solución intuitiva.

He examinado un poco las expresiones regulares y parecen buenas para cuando sabes lo que estás buscando, o al menos la longitud del patrón que estás buscando. Lamentablemente, no sé tampoco.

¿Cómo puedo saber si una cadena se repite y, si es así, cuál es la subsecuencia de repetición más corta?

Aquí hay una solución concisa que evita expresiones regulares y bucles lentos en Python:

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

Consulte la respuesta Wiki de la comunidad iniciada por @davidism para obtener resultados de referencia. En resumen,

La solución de David Zhang es el claro ganador, superando a todos los demás en al menos 5 veces para el gran conjunto de ejemplos.

(Las palabras de esa respuesta, no las mías).

Esto se basa en la observación de que una cadena es periódica si y solo si es igual a una rotación no trivial de sí misma. Felicitaciones a @AleksiTorhamo por darnos cuenta de que luego podemos recuperar el período principal del índice de la primera aparición de sin (s+s)[1:-1], y por informarme de los argumentos opcionales starty endde Python string.find.

Aquí hay una solución usando expresiones 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 los ejemplos en la pregunta:

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)

... produce esta salida:

'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.

La expresión regular (.+?)\1+$se divide en tres partes:

1. (.+?)es un grupo coincidente que contiene al menos uno (pero lo menos posible) de cualquier personaje (porque +?no es codicioso ).

2. \1+ busca al menos una repetición del grupo correspondiente en la primera parte.

3. $comprueba el final de la cadena, para asegurarse de que no haya contenido adicional que no se repita después de las subcadenas repetidas (y el uso re.match()asegura que no haya texto que no se repita antes de las subcadenas repetidas).

En Python 3.4 y versiones posteriores, puede soltar $y usar re.fullmatch()en su lugar, o (en cualquier Python al menos hasta 2.3) ir a otro lado y usar re.search()con la expresión regular ^(.+?)\1+$, todo lo cual se debe más al gusto personal que a cualquier otra cosa.

Puede hacer la observación de que para que una cadena se considere repetitiva, su longitud debe ser divisible por la longitud de su secuencia repetida. Dado que, aquí es una solución que genera divisores de la longitud desde 1a n / 2inclusive, divide la cadena original en subcadenas con la longitud de los divisores, y prueba la igualdad del 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

EDITAR: en Python 3, el /operador ha cambiado para hacer la división flotante por defecto. Para obtener la intdivisión de Python 2, puede usar el //operador en su lugar. Gracias a @ TigerhawkT3 por llamar mi atención sobre esto.

El //operador realiza la división de enteros tanto en Python 2 como en Python 3, por lo que he actualizado la respuesta para admitir ambas versiones. La parte donde probamos para ver si todas las subcadenas son iguales ahora es una operación de cortocircuito que usa alluna expresión de generador.

ACTUALIZACIÓN: en respuesta a un cambio en la pregunta original, el código ahora se ha actualizado para devolver la subcadena de repetición más pequeña si existe y Nonesi no. @godlygeek ha sugerido usar divmodpara reducir el número de iteraciones en el divisorsgenerador, y el código también se ha actualizado para que coincida con eso. Ahora devuelve todos los divisores positivos de nen orden ascendente, exclusivo de nsí mismo.

Actualización adicional para un alto rendimiento: después de varias pruebas, he llegado a la conclusión de que simplemente probar la igualdad de cadena tiene el mejor rendimiento de cualquier solución de corte o iteración en Python. Por lo tanto, tomé una hoja del libro de @ TigerhawkT3 y actualicé mi solución. Ahora es más de 6 veces más rápido que antes, notablemente más rápido que la solución de Tigerhawk, pero más lento que el de David.

Aquí hay algunos puntos de referencia para las diversas respuestas a esta pregunta. Hubo algunos resultados sorprendentes, incluido un rendimiento muy diferente dependiendo de la cadena que se está probando.

Algunas funciones se modificaron para funcionar con Python 3 (principalmente al reemplazar /con //para asegurar la división de enteros). Si ve algo mal, desea agregar su función o desea agregar otra cadena de prueba, haga ping a @ZeroPiraeus en la sala de chat de Python .

En resumen: hay aproximadamente una diferencia de 50x entre las soluciones de mejor y peor desempeño para el amplio conjunto de datos de ejemplo suministrados por OP aquí (a través de este comentario). La solución de David Zhang es el claro ganador, superando a todos los demás en alrededor de 5 veces para el gran conjunto de ejemplos.

Un par de respuestas son muy lentas en casos extremadamente grandes de "no coincidencia". De lo contrario, las funciones parecen ser iguales o claros ganadores dependiendo de la prueba.

Estos son los resultados, incluidas las parcelas realizadas con matplotlib y seaborn para mostrar las diferentes distribuciones:

Corpus 1 (ejemplos suministrados - conjunto pequeño)

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 (ejemplos suministrados - 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 de borde)

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

Las pruebas y los resultados en bruto están disponibles aquí .

Solución no 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]

Solución no regex más rápida, gracias a @ThatWeirdo (ver comentarios):

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

La solución anterior rara vez es más lenta que la original en un pequeño porcentaje, pero generalmente es un poco más rápido, a veces mucho más rápido. Todavía no es más rápido que el davidismo para cadenas más largas, y la solución regex de cero es superior para cadenas cortas. Sale al más rápido (según la prueba de davidismo en github, vea su respuesta) con cadenas de aproximadamente 1000-1500 caracteres. De todos modos, es confiablemente el segundo más rápido (o mejor) en todos los casos que probé. Gracias ThatWeirdo.

Prueba:

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

Primero, reduzca a la mitad la cadena siempre que sea un duplicado de "2 partes". Esto reduce el espacio de búsqueda si hay un número par de repeticiones. Luego, trabajando hacia adelante para encontrar la cadena repetitiva más pequeña, verifique si dividir la cadena completa por una subcadena cada vez más grande solo da como resultado valores vacíos. Solo las subcadenas length // 2deben ser probadas ya que cualquier cosa que no tenga repeticiones.

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

Esto devuelve la coincidencia más corta o Ninguna si no hay coincidencia.

El problema también puede resolverse O(n)en el peor de los casos con la función de prefijo.

Tenga en cuenta que puede ser más lento en el caso general (UPD: y es mucho más lento) que otras soluciones que dependen del número de divisores n, pero generalmente encuentran fallas antes, creo que uno de los casos negativos para ellos será aaa....aab, donde hayn - 1 = 2 * 3 * 5 * 7 ... *p_n - 1 a 's

Primero que nada necesitas calcular la función de prefijo

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

entonces o no hay respuesta o el período más corto es

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

y solo tienes que verificar si k != n and n % k == 0(si la k != n and n % k == 0respuesta es s[:k], de lo contrario no hay respuesta

Puede verificar la prueba aquí (en ruso, pero el traductor en línea probablemente hará el truco)

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 versión intenta solo aquellas longitudes de secuencia candidatas que son factores de la longitud de la cadena; y usa el *operador para construir una cadena de longitud completa a partir de la secuencia 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

Gracias a TigerhawkT3 por notar que length // 2sin + 1dejaría de coincidir con el ababcaso.

Aquí hay una solución directa, sin expresiones regulares.

Para las subcadenas que scomienzan desde el índice cero, de longitudes de 1 a len(s), verifique si esa subcadena substres el patrón repetido. Esta verificación se puede realizar concatenando substrconsigo misma ratioveces, de modo que la longitud de la cadena así formada sea igual a la longitud de s. Por lo tanto ratio=len(s)/len(substr).

Regrese cuando se encuentre dicha subcadena. Esto proporcionaría la subcadena más pequeña posible, si existe.

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"

Comencé con más de ocho soluciones a este problema. Algunos eran bases en expresiones regulares (match, findall, split), algunos de corte y prueba de string, y algunos con métodos de string (find, count, split). Cada uno tenía beneficios en la claridad del código, el tamaño del código, la velocidad y el consumo de memoria. Iba a publicar mi respuesta aquí cuando noté que la velocidad de ejecución se clasificó como importante, así que hice más pruebas y mejoras para llegar a esto:

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 respuesta parece similar a algunas otras respuestas aquí, pero tiene algunas optimizaciones de velocidad que otros no han usado:

• xrange es un poco más rápido en esta aplicación,
• si una cadena de entrada tiene una longitud impar, no verifique ninguna subcadena de longitud par,
• Al usar s[:n]directamente, evitamos crear una variable en cada bucle.

Me interesaría ver cómo funciona esto en las pruebas estándar con hardware común. Creo que será muy inferior al excelente algoritmo de David Zhang en la mayoría de las pruebas, pero de lo contrario debería ser bastante rápido.

Este problema me pareció muy intuitivo. Las soluciones que pensé que serían rápidas eran lentas. ¡Las soluciones que parecían lentas fueron rápidas! Parece que la creación de cadenas de Python con el operador de multiplicación y las comparaciones de cadenas están altamente optimizadas.

Esta función se ejecuta muy rápidamente (probada y es más de 3 veces más rápida que la solución más rápida aquí en cadenas con más de 100k caracteres y la diferencia aumenta a medida que se repite el patrón). Intenta minimizar la cantidad de comparaciones necesarias para obtener la respuesta:

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]

Tenga en cuenta que, por ejemplo, para la cadena de longitud 8 verifica solo un fragmento de tamaño 4 y no tiene que probar más porque el patrón de longitud 1 o 2 daría como resultado la repetición del patrón de longitud 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'

En la respuesta de David Zhang, si tenemos algún tipo de búfer circular, esto no funcionará: principal_period('6210045662100456621004566210045662100456621')debido al comienzo 621, donde me hubiera gustado que escupiera:00456621 .

Extendiendo su solución podemos usar lo siguiente:

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'

Aquí está el código en python que verifica la repetición de subcadena en la cadena principal dada por el usuario .

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

Salida :

Longitud de su cuerda: 40

La subcadena '00456621' se repite en la cadena '0045662100456621004566210045662100456621'

Entrada :

004608294930875576036866359447

Salida :

Longitud de su cadena: 30

No se han encontrado subcadenas repetidas en la cadena '004608294930875576036866359447'