Как найти длину наибольшего вхождения подвектора в вектор

Question

Есть вектор: std::vector<char> main {'1','2','3','4','5','6','7','8','9'}
И есть, например, вектор std::vector<char> sub {'3','4','5','5','6'}

Как видим, вектор sub входит в main на 2й позиции (считая от нуля)
И длина максимального вхождения - 3 (три) позиции (начала '3','4','5' совпадают, а дальше '5' != '6')

Вопрос:
Как это сделать в коде?

Answer 1

Вся задача сводится лишь к двум последовательным операциям, выплоняющихся в цикле:

поиск первого вхождения
вычисление длинны вхождения

А вот и пример кода с парочкой комментов:

// main.cpp

#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <iostream>
#include <vector>

std::pair<std::vector<int>::const_iterator, size_t>
getBigestMatch(const std::vector<int> &vec, const std::vector<int> &sub) {
  assert(sub.empty() == false);

  // if nothing found return iterator to end and 0 len
  auto retval = std::make_pair(vec.end(), 0);

  for (auto iter = vec.begin(); iter != vec.end(); ++iter) {
    // find first match
    iter = std::find(iter, vec.end(), sub[0]);
    if (iter == vec.end()) {
      break;
    }

    // calculate len of sequence
    int len = 1;
    for (auto found = std::next(iter), compare = std::next(sub.begin());
         found != vec.end() && compare != sub.end() && *found == *compare;
         ++found, ++compare, ++len)
      ;

    // if new sequence bigger then previous, then set it as retval
    if (len > retval.second) {
      retval = std::make_pair(iter, len);
    }
  }

  return retval;
}

int main() {
  std::vector<int> main{1, 2, 3, 4, 5, 6, 7, 8, 9};
  std::vector<int> sub{3, 4, 5, 5, 6};

  auto found = getBigestMatch(main, sub);

  std::cout << std::distance(main.cbegin(), found.first) << " " << found.second
            << std::endl;

  return EXIT_SUCCESS;
}

Answer 2

Посчитайте z-функцию для вектора, состоящего из комбинации sub + "@" + main, где разделитель "@" - символ, не встречающийся в обоих исходных.

vector<int> z_function (string s) {
    int n = (int) s.length();
    vector<int> z (n);
    for (int i=1, l=0, r=0; i<n; ++i) {
        if (i <= r)
            z[i] = min (r-i+1, z[i-l]);
        while (i+z[i] < n && s[z[i]] == s[i+z[i]])
            ++z[i];
        if (i+z[i]-1 > r)
            l = i,  r = i+z[i]-1;
    }
    return z;
}

Теперь найдите максимальное значение z[i+sub.size+1] на диапазоне i=0..main.size-1 (см. раздел "Поиск подстроки в строке" на указанной странице), индекс i укажет на позицию, а то самое макс. z - на длину.

Время линейное O(sub.size + main.size)

БЛОГ НА HUSL

Как найти длину наибольшего вхождения подвектора в вектор

Ответы (2 шт):