¿Cómo puedo encontrar el número de secuencias superpuestas en una cadena con Python?

Tengo una secuencia larga, y me gustaría saber con qué frecuencia ocurren algunas subsecuencias en esta secuencia.

Sé string.count (s, sub) , pero solo cuenta secuencias no superpuestas.

¿Existe una función similar que también cuenta secuencias superpuestas?

Related of "¿Cómo puedo encontrar el número de secuencias superpuestas en una cadena con Python?"

Como alternativa a escribir su propia función de búsqueda, puede usar el módulo re :

 In [22]: import re In [23]: haystack = 'abababa baba alibababa' In [24]: needle = 'baba' In [25]: matches = re.finditer(r'(?=(%s))' % re.escape(needle), haystack) In [26]: print [m.start(1) for m in matches] [1, 3, 8, 16, 18] 

Lo anterior imprime las posiciones de inicio de todas las coincidencias (potencialmente superpuestas).

Si todo lo que necesita es el conteo, lo siguiente debe hacer el truco:

 In [27]: len(re.findall(r'(?=(%s))' % re.escape(needle), haystack)) Out[27]: 5 

Una forma sencilla de entenderlo es:

 def count(sub, string): count = 0 for i in xrange(len(string)): if string[i:].startswith(sub): count += 1 return count count('baba', 'abababa baba alibababa') #output: 5 

Si te gustan los fragmentos cortos, puedes hacerlo menos legible pero más inteligente:

 def count(subs, s): return sum((s[i:].startswith(subs) for i in xrange(len(s)))) 

Esto utiliza el hecho de que Python puede tratar los valores booleanos como enteros.

Esto debería ayudarte a:

 matches =[] st = 'abababa baba alibababa' needle = 'baba' for i in xrange(len(st)-len(needle)+1): i = st.find(needle,i,i+len(needle)) if(i >= 0): matches.append(st.find(needle,i,i+len(needle))) print(str(matches)) 

Véalo aquí: http://codepad.org/pmkKXmWB

No lo evaluó para cadenas largas, vea si es lo suficientemente eficiente para su uso.

Hoy aprendí que podría usar un índice de ejecución para obtener la próxima aparición de su subcadena:

 string = 'bobobobobobobob' # long string or variable here count = 0 start = 0 while True: index = string.find('bob', start) if index >= 0: count += 1 start += 1 else: break print(count) 

Devoluciones 7