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 y
end = 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)
a ab aba abab ababc a ab
Complejidad del tiempo:
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