Programa de Python para encontrar índices de substrings superpuestas

Para contar el número de substrings superpuestas en Python, podemos usar el módulo Re. Para obtener los índices usaremos el método re.finditer(). Pero solo devuelve el recuento de índices que no se superponen.

Ejemplos:

Entrada: String: «geeksforgeeksforgeeks»; Patrón: «geeksforgeeks»
Salida: [0, 8]
Explicación: el patrón se superpone a la string desde el índice 0 hasta el índice 12 y nuevamente se superpone desde el índice 8 hasta el índice 20. Por lo tanto, la salida son las posiciones iniciales de superposición, es decir, el índice 0 y el índice 8.  

Entrada: String: “barfoobarfoobarfoobarfoobarfoo” ; Patrón: «foobarfoo»
Salida: [3, 9,15, 21]
Explicación: el patrón se superpone a la string de los índices 3, 9, 15 y 21.

Este método devuelve el recuento de índices que no se superponen solo a partir de una string que tiene un patrón superpuesto de varias apariciones. A continuación se muestra un programa que describe el uso del método finditer() .

# Import required module
import re
  
  
# Function to depict use of finditer() method
def CntSubstr(pattern, string):
  
    # Array storing the indices
    a = [m.start() for m in re.finditer(pattern, string)]
    return a
  
  
# Driver Code
string = 'geeksforgeeksforgeeks'
pattern = 'geeksforgeeks'
  
# Printing index values of non-overlapping pattern
print(CntSubstr(pattern, string))

Producción:

[0]

Por lo tanto, para obtener los índices superpuestos también debemos escapar de las expresiones regulares en el patrón. La definición en la función explícita ayuda a seleccionar los caracteres de forma parcial.

Acercarse:

1. re.finditer() ayuda a encontrar los índices donde ocurre el objeto de coincidencia. Como devuelve un objeto iterable, el método start() ayuda a devolver los índices o, de lo contrario, mostraría que se ha encontrado un objeto coincidente en alguna ubicación.
2. El método estándar para hacer coincidir el uso del módulo re es codicioso, lo que significa que se hace coincidir el número máximo de caracteres. Por lo tanto, el ?={0} ayuda en el número mínimo de coincidencias.
3. Para hacerlo coincidir de modo que coincidan los caracteres parciales, re.escape() ayuda a escapar los caracteres especiales que se agregaron antes, como ? ={0} .
4. El resultado es que al agregar algunas modificaciones, el método finditer() devuelve una lista de índices superpuestos.

A continuación se muestra la implementación del enfoque anterior:

# Import required module
import re
  
  
# Explicit function to Count
# Indices of Overlapping Substrings
def CntSubstr(pattern, string):
    a = [m.start() for m in re.finditer(
        '(?={0})'.format(re.escape(pattern)), string)]
    return a
  
  
# Driver Code
string1 = 'geeksforgeeksforgeeks'
pattern1 = 'geeksforgeeks'
  
string2 = 'barfoobarfoobarfoobarfoobarfoo'
pattern2 = 'foobarfoo'
  
  
# Calling the function
print(CntSubstr(pattern1, string1))
print(CntSubstr(pattern2, string2))

Producción:

[0, 8]
[3, 9, 15, 21]