Подсчет вхождений подмассива в больший массив — обычная задача в программировании. В этой статье блога мы рассмотрим различные методы решения этой проблемы и предоставим примеры кода для каждого подхода. К концу этой статьи вы получите полное представление о различных методах подсчета появления определенного подмассива в массиве.

Метод 1: подход грубой силы
Подход грубой силы включает в себя перебор каждого элемента массива и проверку, соответствует ли подмассив, начинающийся с этого элемента, данному подмассиву. Вот пример реализации на Python:

def count_subarray_occurrences(arr, subarr):
    count = 0
    for i in range(len(arr)):
        if arr[i:i+len(subarr)] == subarr:
            count += 1
    return count

Метод 2: техника скользящего окна
Техника скользящего окна обеспечивает оптимизированное решение за счет сокращения ненужных сравнений. Он включает в себя перемещение окна той же длины, что и подмассив, по массиву и проверку совпадений. Вот пример реализации на Python:

def count_subarray_occurrences(arr, subarr):
    count = 0
    window = arr[:len(subarr)]
    if window == subarr:
        count += 1
    for i in range(len(arr) - len(subarr)):
        window = window[1:] + arr[i + len(subarr)]
        if window == subarr:
            count += 1
    return count

Метод 3: метод префиксной суммы
Метод префиксной суммы полезен, когда элементы массива являются числовыми. Он использует массив сумм префиксов для эффективного подсчета вхождений. Вот пример реализации на Python:

def count_subarray_occurrences(arr, subarr):
    prefix_sum = [0] * (len(arr) + 1)
    count = 0
    for i in range(1, len(prefix_sum)):
        prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1]
    for i in range(len(arr)):
        for j in range(i + 1, len(arr) + 1):
            if prefix_sum[j] - prefix_sum[i] == sum(subarr):
                count += 1
    return count

Метод 4: Алгоритм KMP
Алгоритм Кнута-Морриса-Пратта (KMP) — это мощный алгоритм сопоставления строк, который можно адаптировать для эффективного решения проблемы подсчета подмассивов. Вот пример реализации на Python:

def compute_lps_array(pattern):
    lps = [0] * len(pattern)
    length = 0
    i = 1
    while i < len(pattern):
        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
def count_subarray_occurrences(arr, subarr):
    pattern = subarr
    text = arr
    lps = compute_lps_array(pattern)
    count = 0
    i = j = 0
    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == len(pattern):
            count += 1
            j = lps[j - 1]
        elif i < len(text) and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return count

В этой статье мы рассмотрели четыре различных метода подсчета появления данного подмассива в массиве. Эти методы включают в себя метод грубой силы, метод скользящего окна, метод суммы префиксов и алгоритм KMP. Каждый подход имеет свои преимущества и может применяться исходя из конкретных требований задачи. Поняв эти методы и примеры кода, вы теперь сможете эффективно подсчитывать вхождения подмассивов в своих проектах программирования.