algorithm - 模糊位匹配

Question

我有一个很长的位序列，称为 A，还有一个较短的位序列，x。两个长度相同的比特序列，当对齐后，有k或更少的不匹配比特时，即为模糊匹配。我想在 A 中找到 x 的所有此类模糊出现。

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

有人告诉我这可以在 O(n_A * log(n_A)) 中完成，而不管 k。提供的提示是利用快速傅里叶变换。请记住，对于两个输入 和 , 卷积产生 哪里

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

Answer 1

将x取反，将每一位b替换为(-1)**b，进行卷积。我会让你在作业中解释下一步该做什么。