Given a string and a substring, write a Python program to find how many numbers of substrings are there in the string (including overlapping cases). Let’s discuss a few methods below.
Method #1: Using re.findall() Method
Python3
# Python code to demonstrate# to count total number# of substring in stringimport re# Initialising strings = 'ababababa'# Count count of substrings using re.findallres= len(re.findall('(?=(aba))', s))print("Number of substrings", res) |
Number of substrings 4
Method #2: Using startswith()
Python3
# Python code to demonstrate# to count total number# of substring in string# Initialising stringini_str = "ababababa"sub_str = 'aba'# Count count of substrings using startswithres = sum(1 for i in range(len(ini_str)) if ini_str.startswith("aba", i))# Printing resultprint("Number of substrings", res) |
Number of substrings 4
Time Complexity: O(n)
Auxiliary Space: O(1)
Method #3: Using count() Method
Python3
# Python code to demonstrate# to count total number# of substring in string# Initialising stringini_str = "ababababa"sub_str = 'aba'# Count count of substrings using countdef Countofoccurrences(ini_str,sub_str): # Initialize count and start to 0 count = 0 start = 0 # Search through the string till # we reach the end of it while start < len(ini_str): # Check if a substring is present from # 'start' position till the end pos = ini_str.find(sub_str, start) if pos != -1: # If a substring is present, move 'start' to # the next position from start of the substring start = pos + 1 # Increment the count count += 1 else: # If no further substring is present break # return the value of count return count# Printing resultprint("Number of substrings", Countofoccurrences(ini_str,sub_str)) |
Number of substrings 4
Method #4: Using List Comprehension
In this method, we are using a list comprehension to check if the substring is present in the main string or not. We are using the range of length of the main string minus the length of the substring plus 1. We are then checking if the substring present in the main string at the current index is equal to the given substring or not and incrementing the count accordingly.
Python3
# Python code to demonstrate# to count total number# of substring in string# Initializing stringini_str = "ababababa"sub_str = 'aba'# Count count of substrings using list comprehensionres = sum([1 for i in range(len(ini_str)-len(sub_str)+1) if ini_str[i:i+len(sub_str)] == sub_str])# Printing resultprint("Number of substrings", res)#This code is contributed by Edula Vinay Kumar Reddy |
Number of substrings 4
Time Complexity: O(n)
Auxiliary Space: O(1)
Approach#4: Using sliding window
This program uses a sliding window technique to slide a window of size m over the input string ini_str. At each step, it checks if the substring in the window is equal to sub_str, and if it is, it increments the count variable. It slides the window by iterating over the indices of the input string from 0 to n – m + 1.
Algorithm
1. Initialize count variable to 0
2. Find length of the input string ini_str and length of the substring to be counted sub_str
3. Iterate over the indices of the input string from 0 to n – m + 1
4. At each index, extract a substring of length m from ini_str
5. Compare the extracted substring with the sub_str, if it matches, increment the count variable
6. Return the count variable
Python3
ini_str = "ababababa"sub_str = 'aba'count = 0n = len(ini_str)m = len(sub_str)for i in range(n - m + 1): if ini_str[i:i+m] == sub_str: count += 1print("Number of substrings:", count) |
Number of substrings: 4
Time complexity: O(n * m), where n is the length of the input string and m is the length of the substring to be counted. This is because the program iterates over the input string ini_str n – m + 1 times, and at each step, it extracts a substring of length m and compares it with sub_str.
Space complexity: O(1), as it only uses a constant amount of additional space to store the count variable, the length of the input string n, and the length of the substring to be counted m. It does not create any new data structures or use any additional memory proportional to the size of the input.
