Ho una sequenza di bit molto lunga, denominata A e una sequenza di bit più breve, x. Le sequenze a due bit della stessa lunghezza sono sfocate quando dopo averle allineate, ci sono k o meno bit non corrispondenti. Voglio trovare tutte le occorrenze sfocate di x all'interno di A.Corrispondenza fuzzy bit
Finora, ho provato l'approccio ingenuo. Passare attraverso A, quindi per ogni bit, passare attraverso la lunghezza di x, contare il numero di bit non corrispondenti iniziando da quella posizione in A, e se non supera k, riportare quella posizione. Questo algoritmo non è efficiente. Se A ha n_A bit e x ha n_x bit, il tempo di esecuzione è O(n_A * n_x).
Mi è stato detto che questo può essere fatto in O(n_A * log(n_A)) indipendentemente da k. Il suggerimento fornito è quello di utilizzare la trasformata di Fourier veloce. Che affinché i due ingressi 
e 
, convoluzione produce 
dove
simile alla moltiplicazione polinomiale. Non mi è chiaro come usare questo suggerimento. Qualsiasi aiuto sarebbe molto apprezzato.
Fantastico! Grazie. Ora ha molto senso :) – darksky
Penso che quello che intendi qui sia solo per sostituire gli 0 con i -1. Quindi, in effetti, dovremmo sostituire bit b con - (- 1)^b. Ma ho risolto il problema usando questo trucco. Pubblicherò la mia soluzione in pochi giorni per spiegare perché funziona se nessuno risponde. – darksky
Siamo spiacenti di distruggere il tuo impressionante punteggio di 4444 'ma questo è un buon suggerimento - e ovviamente ha funzionato per l'OP. – Floris