Encontrar múltiples apariciones de una cadena dentro de una cadena en Python

¿Cómo encuentro varias apariciones de una cadena dentro de una cadena en Python? Considera esto:

>>> text = "Allowed Hello Hollow" >>> text.find("ll") 1 >>> 

Así que la primera aparición de ll es 1 como se esperaba. ¿Cómo puedo encontrar la próxima aparición de la misma?

La misma pregunta es válida para una lista. Considerar:

 >>> x = ['ll', 'ok', 'll'] 

¿Cómo puedo encontrar todos los ll con sus índices?

Usando expresiones regulares, puede usar re.finditer para encontrar todas las ocurrencias (que no se superponen):

 >>> import re >>> text = 'Allowed Hello Hollow' >>> for m in re.finditer('ll', text): print('ll found', m.start(), m.end()) ll found 1 3 ll found 10 12 ll found 16 18 

Alternativamente, si no desea la sobrecarga de las expresiones regulares, también puede usar repetidamente str.find para obtener el siguiente índice:

 >>> text = 'Allowed Hello Hollow' >>> index = 0 >>> while index < len(text): index = text.find('ll', index) if index == -1: break print('ll found at', index) index += 2 # +2 because len('ll') == 2 ll found at 1 ll found at 10 ll found at 16 

Esto también funciona para listas y otras secuencias.

Creo que lo que estás buscando es string.count

 "Allowed Hello Hollow".count('ll') >>> 3 

Espero que esto ayude
NOTA: esto solo captura ocurrencias no superpuestas

Para el ejemplo de la lista, use una comprensión:

 >>> l = ['ll', 'xx', 'll'] >>> print [n for (n, e) in enumerate(l) if e == 'll'] [0, 2] 

Del mismo modo para cuerdas:

 >>> text = "Allowed Hello Hollow" >>> print [n for n in xrange(len(text)) if text.find('ll', n) == n] [1, 10, 16] 

Esto mostrará una lista de las ejecuciones adyacentes de “ll”, que pueden o no ser lo que desea

 >>> text = 'Alllowed Hello Holllow' >>> print [n for n in xrange(len(text)) if text.find('ll', n) == n] [1, 2, 11, 17, 18] 

FWIW, aquí hay un par de alternativas no RE que creo que son mejores que la solución de Poke .

El primero usa str.index y comprueba ValueError :

 def findall(sub, string): """ >>> text = "Allowed Hello Hollow" >>> tuple(findall('ll', text)) (1, 10, 16) """ index = 0 - len(sub) try: while True: index = string.index(sub, index + len(sub)) yield index except ValueError: pass 

La segunda prueba usa str.find y verifica el centinela de -1 usando iter :

 def findall_iter(sub, string): """ >>> text = "Allowed Hello Hollow" >>> tuple(findall_iter('ll', text)) (1, 10, 16) """ def next_index(length): index = 0 - length while True: index = string.find(sub, index + length) yield index return iter(next_index(len(sub)).next, -1) 

Para aplicar cualquiera de estas funciones a una lista, tupla u otra iterable de cadenas, puede usar una función de nivel superior, una que toma una función como uno de sus argumentos, como esta:

 def findall_each(findall, sub, strings): """ >>> texts = ("fail", "dolly the llama", "Hello", "Hollow", "not ok") >>> list(findall_each(findall, 'll', texts)) [(), (2, 10), (2,), (2,), ()] >>> texts = ("parallellized", "illegally", "dillydallying", "hillbillies") >>> list(findall_each(findall_iter, 'll', texts)) [(4, 7), (1, 6), (2, 7), (2, 6)] """ return (tuple(findall(sub, string)) for string in strings) 

Para su ejemplo de lista:

 In [1]: x = ['ll','ok','ll'] In [2]: for idx, value in enumerate(x): ...: if value == 'll': ...: print idx, value 0 ll 2 ll 

Si desea todos los elementos de una lista que contenga ‘ll’, también puede hacerlo.

 In [3]: x = ['Allowed','Hello','World','Hollow'] In [4]: for idx, value in enumerate(x): ...: if 'll' in value: ...: print idx, value ...: ...: 0 Allowed 1 Hello 3 Hollow 
 >>> for n,c in enumerate(text): ... try: ... if c+text[n+1] == "ll": print n ... except: pass ... 1 10 16 

Nuevo en progtwigción en general y trabajando a través de un tutorial en línea. También me pidieron que hiciera esto, pero solo usando los métodos que había aprendido hasta ahora (básicamente cuerdas y bucles). No estoy seguro de si esto agrega algún valor aquí, y sé que esto no es cómo lo harías, pero conseguí que funcionara con esto:

 needle = input() haystack = input() counter = 0 n=-1 for i in range (n+1,len(haystack)+1): for j in range(n+1,len(haystack)+1): n=-1 if needle != haystack[i:j]: n = n+1 continue if needle == haystack[i:j]: counter = counter + 1 print (counter) 

Esta versión debe ser lineal en la longitud de la cadena, y debe estar bien siempre que las secuencias no sean demasiado repetitivas (en cuyo caso puede reemplazar la recursión con un bucle while).

 def find_all(st, substr, start_pos=0, accum=[]): ix = st.find(substr, start_pos) if ix == -1: return accum return find_all(st, substr, start_pos=ix + 1, accum=accum + [ix]) 

La lista de comprensión de bstpierre es una buena solución para secuencias cortas, pero parece tener una complejidad cuadrática y nunca termina en un texto largo que estaba usando.

 findall_lc = lambda txt, substr: [n for n in xrange(len(txt)) if txt.find(substr, n) == n] 

Para una cadena aleatoria de longitud no trivial, las dos funciones dan el mismo resultado:

 import random, string; random.seed(0) s = ''.join([random.choice(string.ascii_lowercase) for _ in range(100000)]) >>> find_all(s, 'th') == findall_lc(s, 'th') True >>> findall_lc(s, 'th')[:4] [564, 818, 1872, 2470] 

Pero la versión cuadrática es unas 300 veces más lenta.

 %timeit find_all(s, 'th') 1000 loops, best of 3: 282 µs per loop %timeit findall_lc(s, 'th') 10 loops, best of 3: 92.3 ms per loop 
 #!/usr/local/bin python3 #-*- coding: utf-8 -*- main_string = input() sub_string = input() count = counter = 0 for i in range(len(main_string)): if main_string[i] == sub_string[0]: k = i + 1 for j in range(1, len(sub_string)): if k != len(main_string) and main_string[k] == sub_string[j]: count += 1 k += 1 if count == (len(sub_string) - 1): counter += 1 count = 0 print(counter) 

Este progtwig cuenta el número de todas las subcadenas, incluso si se superponen sin el uso de expresiones regulares. Pero esta es una implementación ingenua y para obtener mejores resultados en el peor de los casos, se recomienda pasar por el árbol de sufijos, KMP y otras estructuras de datos y algoritmos de coincidencia de cadenas.

Aquí está mi función para encontrar múltiples ocurrencias. A diferencia de las otras soluciones aquí, admite los parámetros opcionales de inicio y fin para el corte, al igual que str.index :

 def all_substring_indexes(string, substring, start=0, end=None): result = [] new_start = start while True: try: index = string.index(substring, new_start, end) except ValueError: return result else: result.append(index) new_start = index + len(substring) 

Un código iterativo simple que devuelve una lista de índices donde ocurre la subcadena.

  def allindices(string, sub): l=[] i = string.find(sub) while i >= 0: l.append(i) i = string.find(sub, i + 1) return l 

Puede dividir para obtener posiciones relativas, luego sumr números consecutivos en una lista y agregar (longitud de cadena * orden de ocurrencia) al mismo tiempo para obtener los índices de cadena deseados.

 >>> key = 'll' >>> text = "Allowed Hello Hollow" >>> x = [len(i) for i in text.split(key)[:-1]] >>> [sum(x[:i+1]) + i*len(key) for i in range(len(x))] [1, 10, 16] >>> 

Tal vez no sea tan pythonico, sino algo más autoexplicativo. Devuelve la posición de la palabra buscada en la cadena original.

 def retrieve_occurences(sequence, word, result, base_counter): indx = sequence.find(word) if indx == -1: return result result.append(indx + base_counter) base_counter += indx + len(word) return retrieve_occurences(sequence[indx + len(word):], word, result, base_counter) 

Este enlace explica cómo hacerlo todo en O (n) e incluye también una solución en Python.

Si vas más abajo en los conjuntos de ‘ Árboles de sufijo ‘, podrías hacer lo mismo si tuvieras una cadena grande pero quisieras buscar miles de patrones en ella.

Creo que no hay necesidad de probar la longitud del texto; solo sigue encontrando hasta que no quede nada para encontrar. Me gusta esto:

  >>> text = 'Allowed Hello Hollow' >>> place = 0 >>> while text.find('ll', place) != -1: print('ll found at', text.find('ll', place)) place = text.find('ll', place) + 2 ll found at 1 ll found at 10 ll found at 16 

También puedes hacerlo con la comprensión de la lista condicional de esta manera:

 string1= "Allowed Hello Hollow" string2= "ll" print [num for num in xrange(len(string1)-len(string2)+1) if string1[num:num+len(string2)]==string2] # [1, 10, 16] 

Hace un tiempo había tenido esta idea al azar. El uso de un bucle While con empalme de cadenas y búsqueda de cadenas puede funcionar, incluso para cadenas superpuestas.

 findin = "algorithm alma mater alison alternation alpines" search = "al" inx = 0 num_str = 0 while True: inx = findin.find(search) if inx == -1: #breaks before adding 1 to number of string break inx = inx + 1 findin = findin[inx:] #to splice the 'unsearched' part of the string num_str = num_str + 1 #counts no. of string if num_str != 0: print("There are ",num_str," ",search," in your string.") else: print("There are no ",search," in your string.") 

Soy un aficionado en la progtwigción de Python (progtwigción de cualquier idioma, en realidad), y no estoy seguro de qué otros problemas podría tener, pero creo que está funcionando bien.

Supongo que lower () también podría usarse en algún lugar si es necesario.