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.

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``````