测试是否存在整数k以添加到一个序列以使其成为另一个序列的子序列

Question

假设序列 $ a $ 包含 $ n $ 整数 $ a_1，a_2，a_3，\ ldots，a_n $ 和sequence $ 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 $ 作为哈希表。对于每个元素 $ 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

这里是一个不会始终工作的启发式，但如果从足够大的空间随机选择阵列中的整数，则应使用高概率。

初始化计数 $ c $ 到所有零的哈希表。然后，重复 $ t $ 时间：随机选择 $ i，j $ ，compute $ b_j-a_i $ ，递增 $ c [b_j-a_i] $ 。最后，按数量排序 $ c $ ，从最大计数到最小;然后，对于 $ c [k'] $ ，尝试 $ k'$ 作为您猜测 $ k $ ，并验证每个猜测。

注意：在每次迭代中，递增 $ c [k] $ 的概率至少是 $ 1 / m $ ;如果<跨越类=“math-container”> $ l \ ne k $ ，我们期待 $ c [l] $ 递增更多很少（假设阵列中的整数是随机且足够大的）。因此，在 $ t $ 迭代之后，我们预期 $ \ mathbb {e} [c [k]] \ ge t / M $ 但 $ \ mathbb {e} [c [l]] \ ll t / m $ 。因此，一旦<跨度类=“math-container”> $ t $ 足够大， $ c [k] $ 应该大于其他进入 $ c $ 。

$ t $ 需要是多少？我希望<跨越类=“math-container”> $ t= o（m \ log m）$ 应该足够，基于计数 $ c [l] $ ，假设我们愿意接受误差的概率（这可以是指数级为小的）。 Big-O表示法隐藏的恒定因素可能是非微不足道的。

这只是一个启发式，肯定会在它失败的地方。

Answer 2

以下是在 $ \ mathcal {o}中运行的算法（n \ sqrt {n} + m \ log m）$ 时间。

let $ w $ 表示整数 $ t $ 的函数，计算成对的数量它们的区别是 $ t $ ： $ w（t）=ltvert \ {（x，y）：x \在a，y \中，yx= t \} \ rfter $ 。如果我们访问 $ w（t）$ 我们可以简单地找到它的最大值，看它是 $ n $ 与否。主要思想是使用快速傅立叶变换来估算<跨度类=“数学容器”> $ W $ 。如果数字界限界定，它将产生精确的解决方案，否则，可以使用模数到足够大的数字，然后在找到后验证解决方案。

让 $ n，m $ 是整数（稍后定义）， $ u，v \ in \ mathbb {r} ^ n $ 是矢量定义为的矢量 $$ u [i]=ltvert \ {x \在a \ colon m-x \ seciv i \ pmod n \} \ rfter $$ $$ v [i]=ltvert \ {y \在b \ colon m + y \ seciv i \ pmod n \} \ rfter $$ 让 $ w= u * v $ 表示这两个向量的循环卷积。然后，如果存在 $ k $ 这样 $$ \ forall x \在a中存在y \ In b：y-x= k，$$ 然后我们可以得出结论 $$ w [k \ bmod n]=sum_ {i：v [i] \ neq 0} v [i] u [ik \ bmod n]= n $$ 通过施工是 $ w $ 可以达到的最大值。因此，我们只需要检查 $ \ max_i w（i）= n $ 。然后，我们通过检查原始元素来验证解决方案的正确性。计算 $ w $ 可以通过fft和enverse fft在 $ \ mathcal {o}（n \ log n）$ 时间，然后找到最大元素和验证它需要 $ n $ 步骤，因此总体 $ \ mathcal {O}（n \ log n）$ 时间和空间。

如果两个集中的数字由 $ n $ 这是一个精确的解决方案。 但如果你选择 $ n $ 太小， $ w（i）= n $ 可能会发生碰撞。 因此，我们可以验证 $ w（i）\ ge $ 的所有索引的所有元素;可能有几个，但它们的号码可以束缚。要具有 $ \ ell $ 这样的指标，必须至少有 $ 1 + 2 + \ dots + \ ell $ 碰撞，意味着 $$ p [\ ltvert \ {i \ colon w [i] \ ge n \} \ revert \ ge \ ell] \ le p [\ text {＃consfrisions} \ ge（ \ ell + 1）\ ell / 2]。$$ $ nm $ $ a $ 和 $ b $ 。如果我们选择一个素数 $ n $ ，例如 $ n> 2m $ ，并选择 $ M $ 从 $ \ {1，\ dots，n \} $ ，碰撞概率界定by $ 1 / 2m $ ，因此Markov的不等式是 $$ \ 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 $ 在没有验证的情况下单独的算法实例，并拍摄 $ w [i] \ ge n $ （通过 $ m $ ）。如果有人可以显示每次 $ 1/2 $ 或其他一些常数每次都会下降的共享碰撞的数量，这将显示 $ \ mathcal {o}（m \ log ^ 2 m）$ 。
一个人可以为 $ u $ 和 $ v $ 和使用来构造更好的散列机制 马尔可夫的更高时刻并使浓度锐利。

尽管如此，如果您正在寻找实用的解决方案，这种算法可以正常工作。例如，WORS

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 $ 与offset $ 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） let $ 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]=ltvert \ {j \在i \ colon j> i，b_j - b_i \ text {可被} \ ell \} \ rvert $$ 然后， $ r [i] $ 可以基于 $ r [i'] $ 跨越类=“math-container”> $ i'> i $ ，新索引集 $ i'$ ，是 $ r [i] \ ge n / s $ 。此步骤的成本由 $ o（m）$ 界定。

案例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 $ ，然后选择下半部分 $ a'= a [1：n / 2] $ 重复（否则选择上半部分，相同的参数将遵循）。 递归计算 $ 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 \ i $ 是一组索引 $ j_i={i= j_1， \ dots，j_ {n / 2} \} \ subseteq b $ ，该映射 $ a'$ 到 $ b $ 最多一些偏移量。 col

讲话，至少<跨度类=“math-container”> $ 3m $ 索引： $$ \ sum_ {i \ In i} | j_i |= | I | N / 2 \ GE 6M / N \ CDOT N / 2= 3M $$ 由于<跨越类=“math-container”> $ | b | b |= m $ ，通过倒置原理，至少有一个索引 $ x \ in b $ < / span>出现在3个单独的解决方案中： $$ \存在于b，r，s，p \ In i \ colon \中; x \ in j_r \ cap j_s \ cap j_p $$

让 $ s $ 是三个 $ r 的中位数。由于 $ x \以j_s $ ，而 $ | j_s |= n / 2 $ ， $ x $ 分区 $ j_s $ 到两个部分，其中一个应该小于 $ n / 4 $ 索引，我们假设是下部： $$ j_s={j_1= s，j_2，\ dots，j_ \ ell= x}，\ ell \ le n / 4 $$ 通过施工，<跨越类=“math-container”> $ s= j_1 $ 被映射到 $ a_1 $ ，最多为 $ a_ \ ell $ 最多一些偏移量。但我们也有 $ x \在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）$ 。添加排序成本，并且由于<跨度类=“math-container”> $ m> n $ ，整体复杂性被排序时间 $ o（m \ log m）$