Finding All Occurrences of a Substring in Python

Often, when working with strings, you need to identify all instances of a particular substring, not just the first one. Python’s built-in string methods like find() and rfind() only locate the first occurrence from the beginning or end of the string, respectively. This tutorial will explore various methods to find all occurrences of a substring within a larger string.

Using a `while` Loop with `string.find()`

The most straightforward approach involves using a while loop in combination with the find() method. The find() method returns the lowest index in the string where the substring is found. If the substring is not found, it returns -1. We can repeatedly call find() starting from the last found index to locate all occurrences.

def find_all_occurrences(text, substring):
    """
    Finds all starting indices of a substring within a text.

    Args:
        text: The string to search within.
        substring: The substring to search for.

    Returns:
        A list of integers representing the starting indices of all occurrences
        of the substring in the text.  Returns an empty list if the substring
        is not found.
    """
    indices = []
    start = 0
    while True:
        index = text.find(substring, start)
        if index == -1:
            break
        indices.append(index)
        start = index + 1  # Move past the current occurrence
    return indices

# Example usage:
text = "test test test test"
substring = "test"
occurrences = find_all_occurrences(text, substring)
print(occurrences)  # Output: [0, 5, 10, 15]

text = "banananassantana"
substring = "na"
occurrences = find_all_occurrences(text, substring)
print(occurrences) # Output: [2, 4, 6, 14]

In this code:

We initialize an empty list indices to store the starting indices of the found substrings.
We start searching from index 0.
The while loop continues as long as text.find() returns a valid index (not -1).
Inside the loop, we append the found index to the indices list.
We update the start variable to index + 1 to search for the next occurrence after the current one. To find overlapping occurrences, you would increment start by only 1.

Using Regular Expressions with `re.finditer()`

Python’s re module provides powerful regular expression operations. The re.finditer() function returns an iterator yielding match objects for all non-overlapping matches of a pattern in a string.

import re

def find_all_occurrences_regex(text, substring):
    """
    Finds all starting indices of a substring within a text using regular expressions.

    Args:
        text: The string to search within.
        substring: The substring to search for.

    Returns:
        A list of integers representing the starting indices of all occurrences
        of the substring in the text.
    """
    indices = [m.start() for m in re.finditer(re.escape(substring), text)]
    return indices

# Example usage:
text = "test test test test"
substring = "test"
occurrences = find_all_occurrences_regex(text, substring)
print(occurrences)  # Output: [0, 5, 10, 15]

Key improvements and explanations:

re.escape(): The re.escape() function is crucial when the substring might contain special regular expression characters (e.g., *, ?, ., +, [], ()). It ensures that these characters are treated literally and not as regex metacharacters.
List Comprehension: The [m.start() for m in re.finditer(...)] uses a list comprehension for concise code. m.start() returns the starting index of each match object m.

Using a Generator for Efficiency

If you only need to iterate through the occurrences once, a generator function can be more efficient than building a complete list. Generator functions use the yield keyword to produce values on demand, saving memory.

def find_all_occurrences_generator(text, substring):
    """
    Yields all starting indices of a substring within a text.

    Args:
        text: The string to search within.
        substring: The substring to search for.

    Yields:
        The starting index of each occurrence of the substring in the text.
    """
    start = 0
    while True:
        index = text.find(substring, start)
        if index == -1:
            break
        yield index
        start = index + 1

# Example usage:
text = "test test test test"
substring = "test"
for index in find_all_occurrences_generator(text, substring):
    print(index)  # Output: 0, 5, 10, 15

Choosing the Right Method

For simple substring searches without regular expression needs, the while loop with string.find() or the generator function provide the most straightforward and efficient solutions.
If you need to use regular expressions for more complex pattern matching, the re.finditer() approach is the way to go. Remember to use re.escape() if your search string might contain special regex characters.
If memory usage is a concern and you only need to iterate through the occurrences once, the generator function is the best option.