模糊比特匹配

Question

我有一个非常长的位序列，称为A，和一个较短的位序列x。当对齐它们后，存在k个或更少的不匹配位时，相同长度的两个位序列模糊匹配。我希望找到所有这样的x在A中的模糊出现。

到目前为止，我尝试了朴素的方法。循环遍历A，然后对于每个位，循环遍历x的长度，在A中从该位置开始计算不匹配的位数，如果不超过k，则报告该位置。这种算法效率低下。如果A有n_A位，x有n_x位，则运行时间为O(n_A * n_x)。

据说无论k是多少，这可以在O(n_A * log(n_A))内完成。提供的提示是利用快速傅里叶变换。请记住，对于两个输入和，卷积产生，

类似于多项式乘法。我不清楚如何使用此提示。任何帮助都将不胜感激。

- darksky

---

测试........... - undefined

测试评论........... - undefined

Answer 1

将 x 反转，替换每个位 b 为 (-1)**b，并进行卷积。关于接下来要做什么，我会留给你的作业进行解释。

- David Eisenstat

---

太棒了！谢谢你。现在我理解了很多 :) - darksky

我认为你的意思是将0替换为-1。因此，实际上，我们应该用-（-1）^ b替换位b。但是我已经使用这个技巧解决了问题。如果没有人回答，我会在几天内发布自己的解决方案来解释它为什么有效。 - darksky

很抱歉破坏了你惊人的得分 4444，但这是一个好的提示 - 显然对原帖作者有效。 - Floris