CountSubsegments.md

Разбор задачи CountSubsegments

Условие

Вам надо написать функцию CountSubsegments, которая принимает итераторы двух контейнеров и возвращает количество вхождений второго контейнера в качестве подотрезка внутри первого.

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

std::vector<int> v{1, 1, 2, 10, 1, 0, 1, 2};
std::set<int> s{1, 2};
size_t result = CountSubsegments(v.begin(), v.end(), s.cbegin(), s.cend()); // result == 2

Считайте, что пустой интервал входит в другой итервал столько раз, какова длина второго интервала. Постарайтесь воспользоваться подходящим вспомогательным алгоритмом стандартной библиотеки - написать такой код будет быстрее.

Сдайте только код функции CountSubsegments и подключите необходимые библиотеки. Ваша функция будет скомпилирована с нашей функцией main.

Решение

Прежде всего определимся с заголовком функции. Эта функция должна быть шаблонной, причём типы двух первых и двух последних аргументов могут отличаться (это могут быть итераторы разных контейнеров):

template <typename Iter1, typename Iter2>
size_t CountSubsegments(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2);

Чтобы тип size_t был доступен, надо подключить заголовок cstddef (или любой другой заголовок, в котором подключается cstddef).

Далее вспомним, что в стандартной библиотеке имеется алгоритм std::search, который ищет первое вхождение подпоследовательности в последовательность. Воспользуемся им. Если этот алгоритм вернул итератор, отличный от last1, то очередное вхождение найдено. В этом случае мы инкрементируем счётчик и сдвигаемся к следующей позиции. Иначе цикл заканчивается.

#include <algorithm>
#include <cstddef>

template <typename Iter1, typename Iter2>
size_t CountSubsegments(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2) {
    size_t result = 0;
    for (auto iter = first1; iter != last1;) {
        iter = std::search(iter, last1, first2, last2);
        if (iter != last1) {
            ++result;
            ++iter;
        }
    }
    return result;
}

Конечно, можно было бы реализовать функцию и без обращения к std::search, но вы бы потратили на написание и отладку больше времени.

Типичная ошибка, которую здесь допускают: если не сдвинуть итератор iter внутри if, то цикл окажется бесконечным. Другая ошибка: std::search путают с алгоритмами std::find_first_of и std::find_end. Алгоритм find_fist_of ищет любой элемент из второй последовательности, а find_end похож на search, но находит последнее вхождение подпоследовательности (двигаясь при этом слева направо). То есть, в этой задаче он будет совсем неэффективен.