Tôi có một chuỗi rất dài các bit, được gọi là A và một chuỗi bit ngắn hơn, x. Hai chuỗi bit có cùng độ dài được kết hợp mờ khi sau khi căn chỉnh chúng, có k hoặc ít bit không khớp hơn. Tôi muốn tìm tất cả các lần xuất hiện mờ của x trong phạm vi A.Kết nối bit mờ
Cho đến giờ, tôi đã thử cách tiếp cận ngây thơ. Lặp qua A, sau đó cho mỗi bit, lặp qua chiều dài của x, đếm số bit không khớp bắt đầu từ vị trí đó trong A và nếu nó không vượt quá k, hãy báo cáo vị trí đó. Thuật toán này không hiệu quả. Nếu A có bit n_A và x có bit n_x, thời gian chạy là O(n_A * n_x).
Tôi được thông báo rằng điều này có thể được thực hiện trong O(n_A * log(n_A)) bất kể k. Gợi ý được cung cấp là sử dụng biến đổi Fourier nhanh. Hãy nhớ rằng cho hai đầu vào 
và 
, chập sản xuất 
nơi
tương tự với phép nhân đa thức. Nó không rõ ràng với tôi làm thế nào để sử dụng gợi ý này. Bất kì sự trợ giúp nào đều được đánh giá cao.
Tuyệt vời! Cảm ơn bạn. Nó làm cho rất nhiều ý nghĩa bây giờ :) – darksky
Tôi nghĩ rằng những gì bạn có ý nghĩa ở đây chỉ là để thay thế 0 với -1's. Vì vậy, trong thực tế, chúng ta nên thay thế bit b bởi - (- 1)^b. Nhưng tôi đã giải quyết vấn đề bằng cách sử dụng thủ thuật này. Tôi sẽ đăng giải pháp của riêng mình trong vài ngày để giải thích lý do tại sao nó hoạt động nếu không có ai trả lời. – darksky
Xin lỗi vì đã phá hủy số điểm tuyệt vời của bạn là '4444' nhưng đây là một gợi ý hay - và rõ ràng là làm việc cho OP. – Floris