1

Передо мной стоит достаточно тривиальная задача: найти все вхождения подмассива в массив. Стандартным методом (на каждой итерации по элементам первоначального массива берём K элементов и сравниваем полученный массив значений с искомым подмассивом длиной K) поиск вхождений в худшем случае занимает O((N-K+1)*K), что приемлемо на небольших входных данных.

Но обработать, увы, таким образом мне предстоит данные внушительные. Я подумал над тем, чтобы реализовать поиск вхождений за О(N), т.е. каким-то образом сохраняя данные о найденных вхождениях и сверяя их на каждом новом шаге. По аналогии с поиском единственного вхождения, где мы сохраняем индекс и счётчик, увеличивая его или обнуляя в зависимости от текущего элемента первоначального массива, и возвращаем сохранённый индекс, когда счётчик достиг длины искомого подмассива.

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


UPD: Пример входных/выходных данных

  • Массив: [1, 2, 3, 4, 5, 1, 1, 2, 3, 1, 2, 3]
  • Подмассив: [1, 2, 3]
  • Выходные данные: [0, 6, 9]
12
  • @ДмитрийПолянин Буду очень признателен 19 мар 2018 в 17:02
  • не не получится... я думал отсортировать, но по всей видимости у вас элементы в массиве имеют определённый порядок, и имеются повторяющиеся элементы. 19 мар 2018 в 17:03
  • напишите пример данных с правильным выводом, так как непонятна структура данных и результат который вы хотите получить 19 мар 2018 в 17:05
  • так как там есть разные варианты, например с сохранением порядка, или без сохранения. и вообще непонятно что такое два вхождения, например... 19 мар 2018 в 17:06
  • 1
    O(n)? Нереально. Необходимо проверять каждую потенциальную подпоследовательность на полное вхождение, т.е. получаем O(n*m), где m - количество найденных кандидатов на вхождение. Поскольку в пределе m = n - k + 1, где k - длина подпоследовательности, имеем O(n^2).
    – Akina
    19 мар 2018 в 17:32

2 ответа 2

1

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

Худший случай достигается при ситуации base = [1,1,1,1,1,1,1,1,1] find = [1,1,1,1]. Но вы думаете что есть алгоритм, который в такой ситуации сработает быстрее? Ну может быть и есть, но подобные 'долгие' ситуации очень редки, если брать все возможности ситуаций. И возможно даже если асимптотически такой алгоритм для таких ситуаций будет работать быстрее, то скорее всего из-за его сложности он будет работать медленнее на базовых ситуациях, что в результате сделает его медленнее в среднем. Вообщем я бы не стал дальше пытаться его оптимизировать.

var base = [1, 1, 1, 2, 3, 4, 5, 6, 1, 1, 2, 3, 1, 1, 2, 3];
var find = [1, 1, 2, 3];
var rez = [];
var yes;

var max = base.length - find.length;

for (var i = 0; i <= max; i++) {
  yes = true;

  for (var j = 0; j < find.length; j++) {
    if (base[i + j] != find[j]) {
      yes = false;
      break;
    }
  }

  if (yes) {
    rez.push(i);
  }
}

console.log(rez);

Обновлено

Для максимально быстрого поиска необходимо использовать конечные автоматы.

Смотрим алгоритм Ахо — Корасик.

8
  • В первом абзаце вопроса я как раз описал, что на данный момент использую именно такой алгоритм) Но за то, что будущим поколениям расписали его - плюс) 20 мар 2018 в 20:15
  • @Kir_Antipov не факт что есть алгоритмы быстрее для худшего варианта 20 мар 2018 в 20:26
  • 1
    Такой алгоритм составляет по паттерну который надо найти конечный автомат для поиска, и ищет уже используя его. При желании можно написать, но как говорил выше это больше вопрос для фриланс сайта. 20 мар 2018 в 20:39
  • 1
    @Kir_Antipov Ловите - nauchforum.ru/studconf/tech/xvi/4308 20 мар 2018 в 20:40
  • 1
    И вот это - ru.wikipedia.org/wiki/Алгоритм_Ахо_—_Корасик 20 мар 2018 в 20:43
1

var arr = [1, 2, 3, 4, 5, 1, 1, 2, 3, 1, 2, 3]
var sub = [1, 2, 3];
var res = [];

var j = 0;
var start = -1;

for (var i = 0; i < arr.length; i++) {
  //console.log(i, arr[i], j, sub[j], start);
  if (start == -1) {
    if (arr[i] == sub[j]) {
      start = i;
      j++;
    } else {
      start = -1;
      j = 0;
    }
  } else {
    if (arr[i] == sub[j]) {
      if (j == sub.length - 1) {
        res.push(start);
        start = -1;
        j = 0;
      } else {
        j++;
      }
    } else {
      start = -1;
      j = 0;
      if (arr[i] == sub[j]) {
        start = i;
        j++;
      }
    }
  }
}
// TODO: fix logic to account for sub consisting of one element

console.log(res);

4
  • Надо добавить ещё одно TODO: если, скажем, хотя бы первые два элемента массива идентичны, то сие дело может отрабатывать не совсем верно. Представьте такую ситуацию: исходный массив = [1, 2, 2, 2, 3, 4, 5]. Подмассив = [2, 2, 3, 4, 5]. res останется пустым в ходе выполнения, хотя должен бы содержать в себе элемент 2) 19 мар 2018 в 20:41
  • Ну да ладно, спасибо большое за помощь! 19 мар 2018 в 20:41
  • Неверно работает при var arr = [1, 1, 1, 2, 3, 4, 5, 1, 1, 2, 3, 1, 2, 3] var sub = [1, 1, 2]; находит только одно решение из двух 20 мар 2018 в 14:21
  • @ДмитрийПолянин Да, я об этом же пишу. Работает корректно в том случае, если подмассив не содержит двух и более подряд идущих одинаковых значений. Но хоть что-то) 20 мар 2018 в 19:13

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.