Найти максимальный подмассив с помощью бинарного поиска

Question

У вас есть два массива arr1 и arr2, вы хотите найти максимальный размер подмассива, который является одновременно подмассивом arr1 и arr2

Например:

arr1 = [3,2,1, 4,5]
arr2 = [1,2,3,4,3,2,1]
return is 3 ([3,2,1])

Эта проблемаимеет решение бинарный поиск , которое обеспечивает сложность

O(nlogn) 

.

Кто-нибудь знает, как подойти к этой проблеме?

Answer 1

Итак, я собираюсь представить общую идею.кто-то отредактирует ответ, если структура предложения не ясна

хорошо, так как же мы узнаем, что здесь применим бинарный поиск, предположим, что в качестве длины выражения мы возьмем mid = (l + (r - l) / 2)самый длинный общий подмассив.Теперь, если у нас есть общий подмассив с длиной L, то должен существовать общий подмассив с длиной меньше L, и если два массива не имеют общего подмассива длины L, у них не может быть общего подмассива любой длины больше, чемL. Итак, теперь реализация бинарного поиска должна быть простой: мы проверяем mid, который является нашей возможной длиной, если существует общий подмассив размера mid, если да, то существует вероятность, что общий подмассив большей длины может существовать, поэтому мысохраните текущую удовлетворенную длину в качестве ответа и сделайте l = mid + 1, чтобы проверить возможную большую длину, и если на некоторой итерации бинарного поиска мы увидим, что не существует общего подмассива длины mid, нет смысла увеличивать нашу длину, поэтому мы идемдля более низкой длины r = mid - 1. Написание кода на c ++

  int l = 1 , r = min(array1.size() , array2.size()); // taking min length of array 1 and array2
  int answer = -1;
  while(l <= r)
  {
      int mid = ( l + ( r - l) / 2);
      if(check(array1 , array2 , mid))
      {
          answer = mid;
          l = mid + 1;
     }
     else
       r = mid - 1;
 }
 cout << answer << "\n";

Теперь возникает проблема, как мы можем проверить, что даны длина L и два массива, если существует общий подмассив в обоихмассивы этой заданной длины L, для этого вы должны знать о хэшеНапример, он пытается присвоить массиву уникальное числовое значение, так что становится легко сравнивать эффективность двух разных массивов, т. е. два одинаковых массива будут иметь одинаковое значение хеш-функции, а разные массивы будут иметь разный хеш.существует такой разный метод хеширования, но, как вы уже догадались, это может быть случай, когда два разных массива имеют одинаковый хеш, который известен как коллизия, поэтому как уменьшить его, мы можем уменьшить его с помощью метода сильного хеша, который уменьшаетвероятность столкновения.Один из этих методов - это скользящий хеш, для более общей идеи проверьте прокручиваемый хеш в Интернете.

Теперь при каждой проверке середины в бинарном поиске вычислите скользящий хэш всего подмассива длины mid и сохранитеэто в структуре данных, как hashtable или set.затем снова вычислите скользящий хеш для всех подмассивов длины mid во втором массиве, но на этот раз при вычислении проверяйте, только если это хеш-значение уже было вычислено и сохранено в вашем массиве данных для подмассивов первого массива, в хеш-таблицеO (1)) или set (среднее время поиска является логарифмическим), если да, то этот общий подмассив средней длины существует, и вы возвращаете true для бинарного поиска, но после каждой проверки окна длины mid во втором массиве вы нене найдя уже существующего хэша, вы возвращаете falseпоэтому при условии, что вы берете хеш-таблицу в качестве структуры данных, общая сложность времени будет

(array1.size () + array2.size ()) * log (min (array1.size (), array2.size ()))

потому что вы итерируете log (min (array1.size (), array2.size ()) раз в бинарном поиске, и в каждой итерации вы проверяете оба массива путем обхода, вычисления скользящего хэша ирегистрация в хеш-таблице т.е. (array1.size () + array2.size ()).