Тест, если существует целое число k, чтобы добавить к одной последовательности, чтобы сделать его подпоследовательностью другой последовательности

Question

Предположим, что последовательность $ a $ содержит $ n $ целые числа $ a_1, a_2, a_3, \ ldots, a_n $ и последовательность $ b $ содержит $ m $ целые числа $ b_1, b_2, b_3, \ ldots, b_m $ . Мы знаем, что $ m \ geq n $ . Мы предполагаем, что мы предполагаем, что оба последовательности $ a $ и $ B $ отсортированы в порядке возрастания.

Какой самый быстрый алгоритм определить, существует ли целое число $ K $ , что последовательность $ a_1 + k, a_2 + k, a_3 + k, \ ldots, a_n + k $ - это подпоследовательность последовательности $ b $ ?

Вот наивный алгоритм, который потребуется $ o (n (m-n)) $ время. Храните последовательность $ b $ как hashtable. Для каждого элемента $ b_j $ $ b $ (кроме крупнейшего $ n $ Элементы), используйте $ b_j-a_1 $ Как ваше предположение на $ K $ ; Вы можете проверить это предположение, проверив ли каждый из $ a_1 + k, \ dots, a_n + k $ находятся в hashtable $ B $ . Это требует $ O (n) $ Ожидаемое время в нужное время на $ K $ , и вы делаете $ mn $ догадки, поэтому в общей сложности ожидаемое время работы - $ O (n (mn)) $ . Можем ли мы сделать лучше?

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

Answer 1

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

Инициализируйте hashtable подсчеты $ C $ для всех нулей. Затем повторите $ T $ Times: Randly Pick $ i, j $ , вычислять $ b_j-a_i $ и увеличение $ c [b_j-a_i] $ . Наконец, сортировать $ C $ по количеству, от наибольшего количества до наименьшего; Затем для каждого из крупнейших немногих значений $ C [K '] $ , попробуйте $ k' $ Как ваше предположение на $ K $ и проверьте каждое предположение.

Обратите внимание, что в каждой итерации вероятность увеличения $ c [k] $ , по крайней мере, $ 1 / m $ ; Принимая во внимание, что если $ l \ ne k $ , мы ожидаем, что $ C [l] $ для увеличения намного больше Редко (при условии, что целые числа в массивах являются случайными и достаточно большими). Таким образом, после $ T $ iTerations, мы ожидаем, что мы рассчитываем $ \ mathbb {e} [c [k]] \ ge t / m $ но $ \ mathbb {e} [c [l]] \ ll t / m $ . Итак, однажды $ T $ достаточно большим, $ C [k] $ должен быть больше, чем все другие Вход в $ C $ .

Насколько велика $ T $ надо быть? Я ожидаю, что $ t= o (m \ log m) $ должен быть достаточно, на основе центрального предельного теорема приближения для подсчета $ C [l] $ , предполагая, что мы готовы принять небольшую вероятность ошибки (что может быть приводится в действие экспоненциально мало). Постоянный фактор, скрытый обозначением Big-O, может быть нетривиальным.

Это только эвристический, и наверняка будет ввода, где он не удается.

Answer 2

Вот алгоритм, работающий в $ \ mathcal {o} (n \ sqrt {n} + m \ log m) $ time.

Пусть $ w $ обозначает функцию, которая для целочисленного $ t $ , считает количество пар Что их разница заключается в $ t $ : $ W (t)=lvert \ {(x, y): x \ {(x, y): x \ \ В a, y \ in b, yx= t \} \ Rverts $ . Если бы у нас был доступ к $ w (t) $ Мы могли бы просто найти его максимум и посмотреть, если это $ n $ или нет. Основная идея состоит в том, чтобы оценить $ w $ с использованием быстрого преобразования Фурье. Если числа ограничены, она будет создавать точное решение, в противном случае можно использовать модуль до достаточно большого количества, а затем проверять решения, как только они найдут.

Пусть $ n, m $ есть целые числа (для определения позже), а $ u, v \ in \ mathbb {r} ^ n $ Быть векторами, определенными как $$ u [i]=lvert \ {x \ in \ colon m-x \ equiv i \ pmod n \} \ Rverts $$ $$ v [i]=lvert \ {y \ in b \ colon m + y \ equiv i \ pmod n \} \ Rverts $$ Пусть $ w= U * V $ обозначает круговую свертку этих двух векторов. Тогда, если есть $ K $ такое, что $$ \ forall x \ in \ существует y \ in b: y-x= k, $$ Тогда мы можем заключить $$ w [k \ bmod n]=sum_ {i: v [i] \ neq 0} v [i] u [ik \ bmod n]= n $$ которые by Construction - это максимальное значение, которое $ W $ может достичь. Поэтому нам нужно проверить, только ли $ \ max_i w (i)= n $ или нет. Затем мы проверяем правильность решения, проверяя оригинальные элементы. Вычисление $ W $ может быть сделано по FFT и обратно FFT в $ \ mathcal {o} (n \ log n) $ time, а затем нахождение максимального элемента и проверки его требует $ n $ Шаги, поэтому общий $ \ mathcal {O} (n \ log n) $ время и пространство.

Если числа в обоих наборах ограничены $ n $ Это точное решение. Но если вы выберете $ n $ слишком маленький, $ w (i)= n $ может произойти из-за столкновения. Таким образом, мы можем проверить все элементы для всех индексов, которые $ w (i) \ ge n $ ; Там может быть несколько из них, но их число может быть ограничено. Чтобы иметь $ \ ELL $ такие индексы, у каждого должен быть, по крайней мере, $ 1 + 2 + \ Dots + \ ell $ столкновения, что подразумевает $$ p [\ lvert \ {i \ clon w [i] \ ge n \} \ rvert \ ge \ els] \ le p [\ text {# столкновения} \ ge ( \ ELL + 1) \ ELL / 2]. $$ Есть $ NM $ Пары элементов $ a $ и $ B $ . Если вы выберете простое число $ n $ такой, что $ n> 2m $ , и выберите $ m $ равномерно у случайных из $ \ {1, \ dots, n \} $ , вероятность столкновения ограничена по 1/2 м $ , так что неравенство Маркова $$ \ le \ frac {nm / n} {\ el ^ 2/2} \ le \ frac {n} {\ ell ^ 2} $$ Таким образом, с вероятностью как можно ближе к $ 1 $ , как вы хотите, $ \ ell=mathcal {o} (\ sqrt {n }) $ . Следовательно, общая сложность времени алгоритма $$ \ mathcal {o} (n \ sqrt {n} + m \ log m) $$ В котором $ m \ log m $ - это шаг FFT и IFFT (так как мы устанавливаем $ n= 2M $ ), и $ n \ sqrt {n} $ - это шаг проверки.

Есть два способа, которыми я вижу, чтобы улучшить это:

1. можно запустить $ \ log n $ Отдельные экземпляры алгоритма без проверки и проводят пересечение максимальных показателей, которые $ m $ ). Если можно показать, что количество общих столкновений падает с помощью $ 1/2 $ или какая-то другая постоянная каждый раз, это покажет общее время работы $ \ mathcal {o} (m \ log ^ 2 m) $ .
2. можно построить лучший механизм хеширования для $ u $ и $ v $ и использовать Более высокие моменты для Маркова и сделать концентрацию острее.

Тем не менее, если вы ищете практическое решение, этот алгоритм может работать просто хорошо. Например, хуже

Поведение T-Case $ \ ell \ Приблизительно \ sqrt {n} $ только когда наборы почти арифметические прогрессии.Если вы выбираете элементы почти случайным образом, гарантия будет намного сильнее.Кроме того, вы можете остановить шаг проверки, как только вы найдете ошибку.

Answer 3

Это совершенно другой алгоритм, который, по которому я считаю, работает в $ O (M \ log m) $ худший случай, и должен работать для целочисленных или действительных чисел.

Давайте предположим, что $ a $ и $ B $ уже в порядке возрастания, в противном случае потратить $ o (n \ log n + m \ log m) $ , чтобы сортировать их. Мы слегка укрепляем требование к алгоритму $ \ mathcal {a} (a, b) $ , чтобы вернуть все индексы $ i $ такой, что $ a $ может быть сопоставлен на $ B $ с компенсацией $ k= b_i-a_1 $ , что означает, что сопоставление начинается на $ B_i $ внутрь. Идея высокого уровня состоит в том, чтобы решить подпростоки, соответствующие подпункте $ a $ и объединить индексы таким образом, чтобы оставаться только допустимые решения.

Рекурсия, однако, зависит от того, насколько близко $ a $ заключается в арифметической прогрессии. Формально, пусть периодичность $ \ tau (a) $ определяется как: $$ \ tau (a)=min \ {s \ in \ mathbb {n} ^ +: a_ {i + s + 1} -a_ {i + s}= a_ {i + 1} - a_i \ text {Для всех действительных} i, s \} $$ В словах, это означает элементы $ a $ , периодически с минимальным циклом $ \ Tau (A) $ , до некоторого смещения.

Case I ( $ \ tau (a) Пусть $ s=tau (a) $ и $ \ ell= a_s - a_1 $ . Рекурсивно вычисляет $ i=mathcal {a} (A [1: S], b) $ . Одно наблюдение состоит в том, что если $ i, j \ in i $ , соответствующий набору индекса $ j_i, j_j $ И $ b_j - b_i=ell $ , наборы индекса $ j_i, j_j $ могут быть Объединенные, чтобы показать $ i \ in \ mathcal {a} (A [1: 2S], b) $ . Это простое последствие $ a $ $ s $ периодический, а $ b_j= b_i + \ ell $ гарантирует, что набор индекса $ j_j $ начинается где $ J_i $ заканчивается. Позволять $$ r [i]=lvert \ {j \ in i \ culon j> i, b_j - b_i \ text {divisible by} \ ell \} \ rverts $$ Затем $ r [i] $ можно вычисляться на основе $ R [I '] $ , < Spaness Class= «Математический контейнер»> $ I '> I $ , а новый индекс $ i' $ , - это индексы, которые $ r [i] \ ge n / s $ . Стоимость для этого шага ограничена $ O (M) $ .

Case II ( $ \ tau (a)> n / 3 $ ) : по определению, для $ s= n / 3 $ должен быть индекс $ i $ что $ a_ {i + 1} -a_i \ neq a_ {i + 1 + s} -a_ {i + s} $ . Если $ i \ le n / 3 $ , у нас будет $ i, i + s \ le 2n / 3 $ < / span> который сертифицирует, что $ \ Tau (A [1: 2n / 3])> N / 3 $ . В противном случае $ I> N / 3 $ подразумевает, что $ \ Tau (A [N / 3: N])> n / 3 $ .

wlog предполагает $ \ Tau (A [1: 2n / 3)> N / 3 $ и выберите нижнюю половину $ i=mathcal {a} (a ', b) $ . Для каждого индекса $ i \ in i $ , проверьте, можно ли найти остальную часть последовательности в $ B $ . Поскольку оба последовательности сортируются, это можно сделать в $ O (n) $ Шаг для каждого индекса, который подразумевает общий $ O (| i | \ cdot n) $ Время для вычисления действительных индексов и вернуть их как $ \ mathcal {a} (a, b) $ Эффективность этого шага зависит от следующего утверждения:

Претензия: $ | i | \ le 6m / n $ , что означает, что решения не слишком много перекрывают.

Доказательство претензий: Мы покажем $ | I |> 6M / N $ приводит к противоречию. Каждый индекс $ i \ in i $ - начальная точка набора индексов $ j_i={i= j_1, \ dots, j_ {n / 2} \} \ subsEtq b $ , эта карта $ a '$ на $ B $ до некоторого смещения. Уполномоченный

Лективно, есть как минимум $ 3M $ Индексы: $$ \ sum_ {i \ in i} | j_i |= | I | N / 2 \ GE 6M / N \ CDOT N / 2= 3M $$ Поскольку $ | B |= m $ , по принципу pigeonhole, есть как минимум один индекс $ x \ in b $ < / span> появляется в 3 отдельных решениях: $$ \ существует x \ in b, r, s, p \ in i \ culon \; x \ in j_r \ cap j_s \ cap j_p $$

Пусть $ s $ Будьте посредством трех $ r . Поскольку $ x \ in j_s $ и $ | j_s |= n / 2 $ , $ x $ разделы $ j_s $ до двух частей, один из которых должен иметь меньше, чем $ n / 4 $ Индексы, которые мы предполагаем, это нижняя часть: $$ j_s={j_1= s, j_2, \ dots, j_ \ ell= x \}, \ els \ le n / 4 $$ По конструкции, $ s= j_1 $ сопоставлен на $ a_1 $ , до $ a_ \ ell $ до некоторого смещения. Но у нас также есть $ x \ in j_p $ , это подразумевает периодичность, меньше, чем $ \ ell \ le n / 4 $ в $ a '$ , который противоречит $ \ Tau (A')> N / 3 $ . (Есть несколько подробностей, которые я добавлю позже)

<Сильная> Общая сложность На каждом этапе рекурсии мы платим $ O (M) $ . Периодичность $ \ TAU (A) $ также может быть вычислена в $ O (n) $ , Вычисление самой длинной суффикса, которая также является префиксом, из $ \ mathrm {diff} (a) $ , то есть массив приращения $ a_2-a_1, \ dots, a_n-a_ {n - 1} $ . Однако размер проблемы уменьшается, по меньшей мере, 1/2 $ на каждом рекурсивом этапе. Там будет $ \ log n $ в худшем случае, что подразумевает временную сложность, ограничено $ O (M \ log n) $ . Добавление расходов сортировки и, поскольку $ m> n $ , общая сложность ограничена временем сортировки $ o (m \ log m) $