と呼ばれる非常に長いビットAシーケンスと、短いビット シーケンス がありますx。同じ長さの 2 つのビット シーケンスは、それらを整列させた後、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。提供されるヒントは、高速フーリエ変換を利用することです。
2 つの入力と
の場合、畳み込みは
どこで生成されるかを思い出してください。
多項式の乗算に似ています。このヒントの使い方がよくわかりません。どんな助けでも大歓迎です。