模糊比特匹配

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，并进行卷积。我会让你在作业中解释下一步该做什么。