programa de Python para calcular el número de todos los posibles subcadenas de una cadena

Aquí, vamos a aprender la forma de calcular el número de todos los posibles subcadenas de una cadena de longitud 1 a n mediante el programa de Python?

Dada una cadena y tenemos que calcular el número de todos los posibles subcadenas de longitud de 1 a n.

Esto se puede hacer de dos maneras:

1) por el Procedimiento General

En este método, primero calculamos todos los posibles subcadena utilizando bucles anidados class. Después de todo lo que cuenta la subcadena que se ha calculado. Sin embargo, este proceso es lento y requiere mucho tiempo si la longitud de la cadena excede demasiado.

Tiempo Complejidad : O (n * n) , n es la longitud de la cadena

2) por la fórmula

En este método, podemos calcular simplemente el número total de posibles subcadenas por una fórmula.

Número total de subseries:

    n + (n-1) + (n-2) + ... + 3 + 2 + 1
= n * (n + 1) / 2

Complejidad de tiempo : O (1) , … Para Constante

Nota: No se recomienda que se debe calcular el número de subcadena por el método general porque for sistema de cadenas más grandes puede llegar a ser no responde. A fin de utilizar la fórmula para calcular el número de subcadenas.

código Python para contar el número de subcadenas de una cadena

def count_substr_by_formula(string):
'''
    This function is used to calculate
    number of all possible substring of
    a string by a formula.
    '''
substring = 0
# length of the given string
n = len(string)
substring = n * (n + 1) // 2
return substring
# Time Complexity : O(1) {constant order}
def general_method(string):
'''
    This function is used to calculate
    number of all possible substring of
    a string by using nested for loops.
    '''
substring = 0
n = len(string)
# List to store all the calculated substrings
substr = []
for i in range(n):
for j in range(i,n):
substr.append(string[i:j])
substring = len(substr)
return substring
# Time Complexity : O(n*n)
# Main Code
if __name__=='__main__':
string = 'IncludeHelp'
print('Total number of substring = %d' % count_substr_by_formula(string))
print('Total number of substring = %d' % general_method(string))

salida

Total number of substring = 66
Total number of substring = 66


Deja un comentario

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