Python program to calculate the number of all possible substrings of a string

Here, we will figure out how to compute the quantity of every single imaginable substring of a string of length 1 to n utilizing python program?

Given a string and we need to compute the quantity of every single imaginable substring of length 1 to n.

This should be possible in two different ways:

1) By General Method:

In this strategy, we initially ascertain all the conceivable substring by utilizing settled for circles. After that check all the substring that we determined. However, this procedure is tedious and takes a ton of time if the length of the string surpasses excessively.

Time Complexity: O(n*n), n is the length of the string.

2) By Formula

In this technique, we can essentially compute the all outnumber of potential substrings by an equation.

All out number of substrings:

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

Time Complexity: O(1), … Steady request

Note: It isn’t prescribed that one ought to compute the quantity of substring by General technique in light of the fact that for bigger strings framework may become non-responsive.

So utilize the recipe to ascertain the number of substrings.

Python code to check a number of substrings of a string:

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 = 'JustTechReview'

    print('Total number of substring = %d' % count_substr_by_formula(string))
    print('Total number of substring = %d' % general_method(string))

Output:

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