Programa de Python para imprimir las substrings que son el prefijo de la string dada

Dada una string, imprime todas las substrings posibles que también son el prefijo de la string dada.

Ejemplos:

Input : ababc         
Output : a, ab, aba, abab, ababc, a, ab
          
Input : abdabc          
Output : a, ab, abd, abda, abdab, abdabc, a, ab          

Enfoque:
Usamos dos variables: inicio y fin para realizar un seguimiento de la substring actual y seguir las siguientes condiciones hasta que start < len(string):

  • Si la substring actual también es el prefijo de la string dada, imprímala e incremente end . Si end == len(string), incrementa el inicio yend = start
  • De lo contrario, el incremento comienza yend = start

Lógica para verificar si la substring actual es un prefijo de la string dada:

string[end] == string[end-start]

Esto hace uso del hecho de que si una substring de longitud L es un prefijo de la string dada, entonces la substring de longitud L+1 obtenida después de incluir el siguiente carácter ch en la secuencia también es un prefijo de la string dada si el carácter en (L+1) el índice en la string es igual a ch .

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

      
# Python3 code to find all possible substrings that 
# are also the prefix of the given string
   
# Function to print all the special substrings
def func(string):
       
    # Used to store the starting and
    # ending index of the substrings
    start, end = 0, 0
       
    while start < len(string):
           
        # If substring is also the prefix
        if string[end] == string[end-start]:
               
            # Print the substring
            print(string[start:end + 1], end= " ")
            end += 1
               
            if end == len(string):
                start += 1
                end = start
           
        # Increment the starting 
        # index of the substring        
        else:
            start += 1
            end = start
               
if __name__ == "__main__":
       
    string = "ababc"
    func(string)
Producción:

a ab aba abab ababc a ab

Complejidad del tiempo: O(n^2)

Publicación traducida automáticamente

Artículo escrito por rituraj_jain y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *