Encuentra las coincidencias más cortas entre dos cuerdas

Tengo un archivo de registro grande y quiero extraer una cadena multilínea entre dos cadenas: start y end .

Lo siguiente es una muestra del inputfile :

 start spam start rubbish start wait for it... profit! here end start garbage start second match win. end 

La solución deseada debe imprimir:

 start wait for it... profit! here end start second match win. end 

Intenté una expresión regular simple pero devolvió todo desde el start spam . ¿Cómo debe hacerse esto?

Edición: Información adicional sobre la complejidad computacional de la vida real :

  • Tamaño real del archivo: 2 GB
  • apariciones de ‘inicio’: ~ 12 M, distribuidas uniformemente
  • apariciones de ‘final’: ~ 800, cerca del final del archivo.

Este regex debe coincidir con lo que quieres:

 (start((?!start).)*?end) 

Utilice el método re.findall y el modificador de una sola línea re.S para obtener todas las ocurrencias en una cadena de varias líneas:

 re.findall('(start((?!start).)*?end)', text, re.S) 

Vea una prueba aquí .

Hazlo con código – máquina de estado básica:

 open = False tmp = [] for ln in fi: if 'start' in ln: if open: tmp = [] else: open = True if open: tmp.append(ln) if 'end' in ln: open = False for x in tmp: print x tmp = [] 

Esto es difícil de hacer porque, de forma predeterminada, el módulo re no busca coincidencias superpuestas. Las versiones más nuevas de Python tienen un nuevo módulo de regex que permite coincidencias superpuestas.

https://pypi.python.org/pypi/regex

Usted querría usar algo como

 regex.findall(pattern, string, overlapped=True) 

Si estás atascado con Python 2.x u otra cosa que no tenga regex , todavía es posible con algunos trucos. Una persona shiny lo resolvió aquí:

¿La expresión regular de Python encuentra todas las coincidencias superpuestas?

Una vez que tenga todas las coincidencias posibles (no codiciosas, imagino) que se superponen, simplemente determine cuál es la más corta, lo que debería ser fácil.

¿Podría hacer (?s)start.*?(?=end|start)(?:end)? , luego filtra todo lo que no termina en “final”.