HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonModerate

Function to find all occurrences of substring

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
occurrencesallsubstringfunctionfind

Problem

This function returns a list of all the beginning indices of a substring in a string. After finding the index of a substring, the search for the next one begins just after this index.

def find_substring(substring, string):
    """ 
    Returns list of indices where substring begins in string

    >>> find_substring('me', "The cat says meow, meow")
    [13, 19]
    """
    indices = []
    index = -1  # Begin at -1 so index + 1 is 0
    while True:
        # Find next index of substring, by starting search from index + 1
        index = string.find(substring, index + 1)
        if index == -1:  
            break  # All occurrences have been found
        indices.append(index)
    return indices

Solution

I would turn this function into a generator so that an iteration over its values does not unnecessarily build a list into memory. If the caller trully needs a list, they can still call list(find_substring(...)). I would also rename this function substring_indexes as I feel it better convey what this function is about; also index could be something like last_known_position or last_found. But naming is hard and I might be wrong on this one.

def substring_indexes(substring, string):
    """ 
    Generate indices of where substring begins in string

    >>> list(find_substring('me', "The cat says meow, meow"))
    [13, 19]
    """
    last_found = -1  # Begin at -1 so the next position to search from is 0
    while True:
        # Find next index of substring, by starting after its last known position
        last_found = string.find(substring, last_found + 1)
        if last_found == -1:  
            break  # All occurrences have been found
        yield last_found

Code Snippets

def substring_indexes(substring, string):
    """ 
    Generate indices of where substring begins in string

    >>> list(find_substring('me', "The cat says meow, meow"))
    [13, 19]
    """
    last_found = -1  # Begin at -1 so the next position to search from is 0
    while True:
        # Find next index of substring, by starting after its last known position
        last_found = string.find(substring, last_found + 1)
        if last_found == -1:  
            break  # All occurrences have been found
        yield last_found

Context

StackExchange Code Review Q#146834, answer score: 14

Revisions (0)

No revisions yet.