Many times while working with strings, we have problems dealing with substrings. This may include the problem of finding all positions of particular substrings in a string using Python. Let’s discuss specific ways in which this task can be performed.
Input: s = "Lazyroar is best for Geeks", f = "Geeks" Output: [0, 8, 26] Explanation: The start indices of the substrings are : [0, 8, 26]
Occurrences of Substring in the String
Below are the methods that we will cover in this article:
- Using startswith function with list comprehension
- Using re.finditer function
- Using find() Method
- Using string slicing and while loop
- Using re.finditer() with reduce()
Get all occurrences of a Substring in a String using startswith
This task can be performed using the two functionalities. The startswith function primarily performs the task of getting the starting indices of the substring and list comprehension is used to iterate through the whole target string.
Python3
test_str = "Lazyroar is best for Geeks"# initializing substringtest_sub = "Geeks"# printing original stringprint("The original string is : " + test_str)# printing substringprint("The substring to find : " + test_sub)# using list comprehension + startswith()# All occurrences of substring in stringres = [i for i in range(len(test_str)) if test_str.startswith(test_sub, i)]# printing resultprint("The start indices of the substrings are : " + str(res)) |
The original string is : Lazyroar is best for Geeks The substring to find : Geeks The start indices of the substrings are : [0, 8, 26]
Time Complexity: O(n*m), where n is the length of the original string and m is the length of the substring to find
Auxiliary Space: O(k), where k is the number of occurrences of the substring in the string
Count Number of Substring Occurrences in String using re.finditer function
The finditer function of the regex library can help us perform the task of finding the occurrences of the substring in the target string and the start function can return the resultant index of each of them.
Python3
import re# initializing stringtest_str = "Lazyroar is best for Geeks"# initializing substringtest_sub = "Geeks"# printing original stringprint("The original string is : " + test_str)# printing substringprint("The substring to find : " + test_sub)# All occurrences of substring in stringres = [i.start() for i in re.finditer(test_sub, test_str)]# printing resultprint("The start indices of the substrings are : " + str(res)) |
The original string is : Lazyroar is best for Geeks The substring to find : Geeks The start indices of the substrings are : [0, 8, 26]
Space complexity: O(n), where n is the length of the original string.
Time complexity: O(n + m), where n is the length of the original string and m is the length of the substring.
Count Number of Substring Occurrences in the String using find()
Here the find method gives the index of the first occurrence of the substring in the string and then with the help of replace method, we replace the main string to string where we have to find the remaining substring and how we get all the substring indexes in the string.
Python3
test_str = "Lazyroar is best for Geeks"# initializing substringtest_sub = "Geeks"# printing original stringprint("The original string is : " + test_str)# printing substringprint("The substring to find : " + test_sub)res=[]while(test_str.find(test_sub)!=-1): res.append(test_str.find(test_sub)) test_str=test_str.replace(test_sub,"*"*len(test_sub),1)# printing resultprint("The start indices of the substrings are : " + str(res)) |
The original string is : Lazyroar is best for Geeks The substring to find : Geeks The start indices of the substrings are : [0, 8, 26]
Time Complexity: O(n*m), where n is the length of the original string and m is the length of the substring.
Auxiliary Space: O(k), where k is the number of occurrences of the substring in the string.
Occurrences of a substring in a string using Slicing
Here we initialize an empty list to store the indices of all occurrences of the substring then set the starting index i to 0. Use a while loop to keep searching for the substring in the string. Inside the while loop, use the find() method to find the first occurrence of the substring in the string, starting from the current index I. If find() returns -1, it means that there are no more occurrences of the substring in the string, so break out of the loop. If find() returns a non-negative value, append the index of the first character of the substring to the list, and update the starting index i to the next character after the end of the substring. Repeat steps 4-6 until there are no more occurrences of the substring in the string.
Return the list of indices.
Python3
def find_all_substrings(string, substring): # Initialize an empty list to store the # indices of all occurrences of the substring. indices = [] # Set the starting index i to 0. i = 0 # Use a while loop to keep searching for # the substring in the string. while i < len(string): # Use the find() method to find the first #occurrence of the substring in the string j = string.find(substring, i) # If find() returns -1, it means that there # are no more occurrences of the substring in # the string, so break out of the loop. if j == -1: break indices.append(j) i = j + len(substring) # Return the list of indices. return indices# Example usage:test_str = "Lazyroar is best for Geeks"test_sub = "Geeks"print(find_all_substrings(test_str, test_sub)) |
[0, 8, 26]
Time complexity: O(nm), where n is the length of the string and m is the length of the substring.
Auxiliary space: O(k), where k is the number of occurrences of the substring in the string.
List All Occurrences of Pattern in String using re.finditer() and reduce()
Import the required modules – re and functools then Initialize the input string test_str and the substring to be searched test_sub. Use re. finder () to find all the occurrences of the substring test_sub in the string test_str.Use reduce() to get the start indices of all the occurrences found in the step. The lambda function inside the reduce() takes two arguments – the first one is the list x that accumulates the start indices and the second one is the Match object y returned by finditer(). The function adds the start index of the current Match object to the list x and converts the final result to a string and prints it.
Python3
import refrom functools import reduce# initializing stringtest_str = "Lazyroar is best for Geeks"# initializing substringtest_sub = "Geeks"# using re.finditer() to find all occurrences of substring in stringoccurrences = re.finditer(test_sub, test_str)# using reduce() to get start indices of all occurrencesres = reduce(lambda x, y: x + [y.start()], occurrences, [])# printing resultprint("The start indices of the substrings are : " + str(res))#This code is contributed by Jyothi pinjala |
The start indices of the substrings are : [0, 8, 26]
Time Complexity: O(n), where n is the length of the input string.
Auxiliary Space: O(m), where m is the number of occurrences of the substring in the input string. This is because we need to store the start indices of all the occurrences in a list.
