Encuentra la secuencia repetitiva más larga en una cuerda

Necesito encontrar la secuencia más larga en una cadena con la advertencia de que la secuencia debe repetirse tres o más veces. Así, por ejemplo, si mi cadena es:

fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld

entonces me gustaría que el valor ” helloworld ” sea devuelto.

Conozco algunas formas de lograrlo, pero el problema al que me enfrento es que la cadena real es absurdamente grande, por lo que realmente estoy buscando un método que pueda hacerlo de manera oportuna.

Este problema es una variante del problema de subcadenas repetidas más largo y hay un algoritmo de tiempo O (n) para resolverlo que utiliza árboles de sufijos . La idea (como lo sugiere Wikipedia) es construir un árbol de sufijos (tiempo O (n)), anotar todos los nodos en el árbol con el número de descendientes (tiempo O (n) usando un DFS), y luego encontrar el El nodo más profundo en el árbol con al menos tres descendientes (tiempo O (n) usando un DFS). Este algoritmo general lleva tiempo O (n).

Dicho esto, los árboles de sufijos son muy difíciles de construir, por lo que probablemente querrá encontrar una biblioteca de Python que implemente árboles de sufijos antes de intentar esta implementación. Una búsqueda rápida en Google convierte esta biblioteca , aunque no estoy seguro de que sea una buena implementación.

¡Espero que esto ayude!

Use defaultdict para calcular cada subcadena que comienza con cada posición en la cadena de entrada. El OP no estaba claro si las coincidencias superpuestas deben o no incluirse, este método de fuerza bruta las incluye.

from collections import defaultdict def getsubs(loc, s): substr = s[loc:] i = -1 while(substr): yield substr substr = s[loc:i] i -= 1 def longestRepetitiveSubstring(r, minocc=3): occ = defaultdict(int) # tally all occurrences of all substrings for i in range(len(r)): for sub in getsubs(i,r): occ[sub] += 1 # filter out all substrings with fewer than minocc occurrences occ_minocc = [k for k,v in occ.items() if v >= minocc] if occ_minocc: maxkey = max(occ_minocc, key=len) return maxkey, occ[maxkey] else: raise ValueError("no repetitions of any substring of '%s' with %d or more occurrences" % (r,minocc)) 

huellas dactilares:

 ('helloworld', 3) 

Comencemos por el final, cuente la frecuencia y pare tan pronto como aparezca el elemento más frecuente 3 o más veces.

 from collections import Counter a='fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld' times=3 for n in range(1,len(a)/times+1)[::-1]: substrings=[a[i:i+n] for i in range(len(a)-n+1)] freqs=Counter(substrings) if freqs.most_common(1)[0][1]>=3: seq=freqs.most_common(1)[0][0] break print "sequence '%s' of length %s occurs %s or more times"%(seq,n,times) 

Resultado:

 >>> sequence 'helloworld' of length 10 occurs 3 or more times 

Edición: si tiene la sensación de que está tratando con entradas aleatorias y la subcadena común debe ser de poca longitud, es mejor que comience (si necesita la velocidad) con subcadenas pequeñas y deténgase cuando no pueda encontrar ninguna que aparezca en menos 3 veces

 from collections import Counter a='fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld' times=3 for n in range(1,len(a)/times+1): substrings=[a[i:i+n] for i in range(len(a)-n+1)] freqs=Counter(substrings) if freqs.most_common(1)[0][1]<3: n-=1 break else: seq=freqs.most_common(1)[0][0] print "sequence '%s' of length %s occurs %s or more times"%(seq,n,times) 

El mismo resultado que el anterior.

La primera idea que vino a la mente es buscar con expresiones regulares cada vez más grandes:

 import re text = 'fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld' largest = '' i = 1 while 1: m = re.search("(" + ("\w" * i) + ").*\\1.*\\1", text) if not m: break largest = m.group(1) i += 1 print largest # helloworld 

El código se ejecutó con éxito. La complejidad del tiempo parece ser al menos O (n ^ 2).

Si invierte la cadena de entrada, aliméntela a una expresión regular como (.+)(?:.*\1){2}
Debería darte la cuerda más larga repetida 3 veces. (Invierta la captura del grupo 1 para la respuesta)

Editar:
Tengo que decir cancelar de esta manera. Depende del primer partido. A menos que se haya probado contra una longitud de curr contra la longitud máxima hasta el momento, en un bucle iterativo, regex no funcionará para esto.

 from collections import Counter def Longest(string): b = [] le = [] for i in set(string): for j in range(Counter(string)[i]+1): b.append(i* (j+1)) for i in b: if i in string: le.append(i) return ([s for s in le if len(s)==len(max( le , key = len))])