Функция, возвращающая позиции вхождения подстроки в строку

Условие

Разработайте функцию, принимающую две строки — основную строку source и подстроку pattern. Функция должна вернуть массив (list) индексов, начиная с нуля, где pattern встречается в source. Если подстрока не найдена, возвращайте пустой массив.

Пример:

find_occurrences("ababa", "aba")  # → [0, 2]

Требования:

• Входные данные — любые строки, включая пустые.
• Поиск должен учитывать перекрывающиеся вхождения.
• Алгоритм должен работать за линейное время относительно длины source в среднем случае.

Ответ

Используйте алгоритм Кнута — Морриса — Пратта: префикс-функция позволяет продолжать поиск без повторного обхода уже проверенных символов. После совпадения нельзя сбрасывать состояние в ноль — нужны перекрытия.

def find_occurrences(source, pattern):
    if not pattern:
        return list(range(len(source) + 1))
    prefix = [0] * len(pattern)
    for i in range(1, len(pattern)):
        j = prefix[i - 1]
        while j and pattern[i] != pattern[j]:
            j = prefix[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        prefix[i] = j
    result, matched = [], 0
    for i, char in enumerate(source):
        while matched and char != pattern[matched]:
            matched = prefix[matched - 1]
        if char == pattern[matched]:
            matched += 1
        if matched == len(pattern):
            result.append(i - len(pattern) + 1)
            matched = prefix[matched - 1]
    return result

Пустой шаблон здесь совпадает на каждой границе строки, включая конец. Для ababa и aba получается [0, 2]. Время O(n + m), дополнительная память O(m), не считая результата.