Python implementation of find_all_indexes I got asked this question before in an interview.

For example, find_all_indexes('ababc', 'abc') returns 2. This Python function should find the index of first occurrence pattern. I also wrote a function that returns a list of starting indexes of all occurrences of the pattern in a text.

I have the following implementation that handles most of the cases:

def find_all_indexes(text, pattern):
    indexes = []
    text_index = 0
    while text_index != len(text):
        if pattern == '':
            indexes.append(text_index)
        else:
            for i in range(len(pattern)):
                if text_index + i &lt; len(text):
                    if text[text_index + i] != pattern[i]:
                        break
                    if i == len(pattern) - 1:
                        indexes.append(text_index)
        text_index += 1
    return indexes

def test_string_algorithms(text, pattern):
    indexes = find_all_indexes(text, pattern)
    print('find_all_indexes({!r}, {!r}) =&gt; {}'.format(text, pattern, indexes))

def main():
    test_string_algorithms(text, pattern)
    print('Usage: {} text pattern'.format(script))
    print("find_all_indexes('abra cadabra', 'abra') =&gt; [0, 8]")

if __name__ == '__main__':
    main()


I am not sure if I exhausted all of the edge cases, but I ran this unit test, and it passed all tests.

The pytest output:



pytest test.py
======================= test session starts ========================
platform darwin -- Python 2.7.12, pytest-3.0.5, py-1.4.32, pluggy-0.4.0

collected 3 items 

test.py .........

===================== 3 passed in 0.07 seconds
The code looks correct but overly complicated for the naïve algorithm used.

For a first refactor, you could pull out the special case pattern == ''. (We might pull it back in later).

Then


            for i in range(len(pattern)):
                if text_index + i &lt; len(text):
                    if text[text_index + i] != pattern[i]:
                        break
                    if i == len(pattern) - 1:
                        indexes.append(text_index)



is just a substring equality check. There are two things to note here:


Since it fails when text_index + len(pattern) &gt; len(text) the outer loop runs too far.
This could be written as if text[text_index:text_index+len(pattern)] == pattern: indexes.append(text_index).


Thirdly, the outer while loop could be written as a for in range, which is more Pythonic.

Putting those together, we have

def find_all_indexes(text, pattern):
    if pattern == '':
        return range(len(text) + 1)

    indexes = []
    for text_index in range(len(text) - len(pattern) + 1):
        if text[text_index : text_index + len(pattern)] == pattern:
            indexes.append(text_index)
    return indexes


But then the Pythonic way to write a for if append loop like that is a comprehension:

def find_all_indexes(text, pattern):
    if pattern == '':
        return range(len(text) + 1)

    return [text_index for text_index in range(len(text) - len(pattern) + 1)
            if text[text_index : text_index + len(pattern)] == pattern]


And now the special case is really a microoptimisation, and could possibly be removed to leave a one-liner.



However, that's not the final word. Naïve string search is asymptotically inferior to techniques such as Knuth-Morris-Pratt string search. You probably shouldn't roll your own KMP routine, but you could use string.find to get the benefit. So a better implementation would be a loop around string.find.