Fuzzy-Bit-Matching

Question

Ich habe eine sehr lange Sequenz von Bits, genannt A, und eine kürzere Sequenz von Bits, x. Zwei Bitfolgen derselben Länge werden unscharf abgeglichen, wenn nach dem Ausrichten k oder weniger nicht übereinstimmende Bits vorhanden sind. Ich möchte alle solche unscharfen Vorkommen von x innerhalb von A finden.

Bisher habe ich den naiven Ansatz ausprobiert. Schleife durch A, dann für jedes Bit, Schleife durch die Länge von x, Zähle die Anzahl der nicht übereinstimmenden Bits beginnend an dieser Position in A, und wenn es k nicht überschreitet, berichte diese Position. Dieser Algorithmus ist nicht effizient. Wenn A n_A Bits hat und x n_x Bits hat, ist die Laufzeit O(n_A * n_x).

Mir wurde gesagt, dass dies in O(n_A * log(n_A)) unabhängig von k getan werden kann. Der bereitgestellte Hinweis besteht darin, die schnelle Fourier-Transformation zu verwenden. Denken Sie daran, dass für zwei Eingänge und , Faltung zu Polynommultiplikation wo

ähnlich produziert. Es ist mir nicht klar, wie ich diesen Hinweis verwenden soll. Jede Hilfe würde sehr geschätzt werden.

Answer 1

Umkehren x, ersetzen Sie jedes Bit b durch (-1) ** b, und falten Sie. Ich werde dich auf deinen Hausaufgaben erklären lassen, was als nächstes zu tun ist.