Подсчёт подстрок

Подсчёт подстрок

Эта задача заключается в подсчёте всех вхождений подстроки в строку, включая перекрывающиеся вхождения. Это важное отличие от встроенной функции count(), которая не считает перекрывающиеся вхождения.

Простое решение

def count_substr(string: str, substring: str) -> int:
    """
    Считает количество вхождений подстроки в строку, включая перекрывающиеся.
    
    Args:
        string: Основная строка для поиска
        substring: Подстрока для поиска
    
    Returns:
        Количество вхождений подстроки
    
    Examples:
        >>> count_substr("abababa", "aba")
        3
        >>> count_substr("hello", "l")
        2
        >>> count_substr("aaa", "aa")
        2
    """
    if not substring or not string:
        return 0
    
    # Перемещаемся по строке и считаем совпадения
    count = 0
    for i in range(len(string) - len(substring) + 1):
        if string[i:i+len(substring)] == substring:
            count += 1
    
    return count

Сравнение с встроенной функцией

# Встроенная функция count() НЕ считает перекрывающиеся
print("abababa".count("aba"))  # 2 (не считает перекрывающиеся)
print(count_substr("abababa", "aba"))  # 3 (считает все)

print("hello".count("l"))  # 2
print(count_substr("hello", "l"))  # 2

print("aaa".count("aa"))  # 1 (только две подряд)
print(count_substr("aaa", "aa"))  # 2 (считает перекрывающиеся)

Решение с использованием find()

def count_substr_with_find(string: str, substring: str) -> int:
    """
    Альтернативное решение, используя метод find().
    """
    if not substring or not string:
        return 0
    
    count = 0
    start = 0
    
    while True:
        # find() возвращает индекс первого совпадения или -1
        pos = string.find(substring, start)
        if pos == -1:
            break
        count += 1
        # Двигаемся на 1 символ, чтобы учесть перекрытия
        start = pos + 1
    
    return count

Решение с использованием регулярных выражений

import re

def count_substr_regex(string: str, substring: str) -> int:
    """
    Решение с использованием регулярных выражений.
    """
    if not substring or not string:
        return 0
    
    # Экранируем специальные символы в подстроке
    escaped = re.escape(substring)
    # (?=...) — позитивная lookahead, позволяет считать перекрытия
    pattern = f"(?={escaped})"
    
    return len(re.findall(pattern, string))

Примеры использования

# Основные примеры
print(count_substr("abababa", "aba"))     # 3
print(count_substr("hello", "l"))        # 2
print(count_substr("aaa", "aa"))         # 2

# Дополнительные примеры
print(count_substr("abcabcabc", "abc"))   # 3
print(count_substr("aaaa", "aa"))        # 3 (позиции 0,1,2)
print(count_substr("hello world", "o"))  # 2
print(count_substr("test", "xyz"))       # 0 (нет совпадений)
print(count_substr("", "a"))             # 0 (пустая строка)
print(count_substr("hello", ""))         # 0 (пустая подстрока)

Оптимизированное решение

def count_substr_optimized(string: str, substring: str) -> int:
    """
    Оптимизированная версия с ранним выходом.
    """
    if not substring or not string or len(substring) > len(string):
        return 0
    
    sub_len = len(substring)
    str_len = len(string)
    count = 0
    
    for i in range(str_len - sub_len + 1):
        # Используем встроенное сравнение (оптимизировано на C уровне)
        if string[i:i+sub_len] == substring:
            count += 1
    
    return count

Решение для больших строк (KMP алгоритм)

def count_substr_kmp(string: str, substring: str) -> int:
    """
    Решение с использованием KMP (Knuth-Morris-Pratt) алгоритма.
    Более эффективно для больших строк и сложных паттернов.
    """
    if not substring or not string or len(substring) > len(string):
        return 0
    
    # Построение таблицы префиксов
    def build_lps(pattern):
        m = len(pattern)
        lps = [0] * m
        length = 0
        i = 1
        
        while i < m:
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        
        return lps
    
    n = len(string)
    m = len(substring)
    lps = build_lps(substring)
    
    count = 0
    i = 0  # индекс для string
    j = 0  # индекс для substring
    
    while i < n:
        if substring[j] == string[i]:
            i += 1
            j += 1
        
        if j == m:
            count += 1
            j = lps[j - 1]  # Для перекрывающихся вхождений
        elif i < n and substring[j] != string[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    
    return count

Тестирование

def test_count_substr():
    # Примеры из задания
    assert count_substr("abababa", "aba") == 3
    assert count_substr("hello", "l") == 2
    assert count_substr("aaa", "aa") == 2
    
    # Граничные случаи
    assert count_substr("", "a") == 0
    assert count_substr("hello", "") == 0
    assert count_substr("", "") == 0
    
    # Нет совпадений
    assert count_substr("hello", "xyz") == 0
    
    # Одно совпадение
    assert count_substr("abc", "abc") == 1
    assert count_substr("hello", "h") == 1
    
    # Все символы
    assert count_substr("aaaa", "a") == 4
    
    # Перекрывающиеся
    assert count_substr("aaaa", "aa") == 3
    assert count_substr("abcabcabc", "abc") == 3
    
    # Длинная подстрока
    assert count_substr("hello", "hello") == 1
    assert count_substr("hello", "helloworld") == 0
    
    print("Все тесты пройдены!")

test_count_substr()

Сравнение производительности

import time

def benchmark():
    # Большая строка для тестирования
    big_string = "abab" * 10000
    
    start = time.time()
    result1 = count_substr(big_string, "aba")
    time1 = time.time() - start
    
    start = time.time()
    result2 = count_substr_with_find(big_string, "aba")
    time2 = time.time() - start
    
    start = time.time()
    result3 = count_substr_kmp(big_string, "aba")
    time3 = time.time() - start
    
    print(f"Простое решение: {time1:.6f}s, результат: {result1}")
    print(f"С find(): {time2:.6f}s, результат: {result2}")
    print(f"KMP: {time3:.6f}s, результат: {result3}")

benchmark()

Анализ сложности

Простое решение:

• Временная сложность: O(n·m), где n — длина строки, m — длина подстроки
• Пространственная сложность: O(1)

KMP алгоритм:

• Временная сложность: O(n + m)
• Пространственная сложность: O(m)

Для большинства практических случаев простое решение достаточно эффективно. KMP рекомендуется для очень больших строк и сложных паттернов.