模糊比特匹配

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，用（-1）** b替換每個位b並進行卷積。我會讓你解釋你的作業下一步該做什麼。