我有一个很长的位序列,称为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
. 提供的提示是利用快速傅里叶变换。请记住,对于两个输入和
,卷积
产生
类似于多项式乘法。我不清楚如何使用这个提示。任何帮助将非常感激。