Calculating similarity between bit strings/signal
You should indeed look into sequence alignment methods used in bioinformatics. Those can penalize both for insertions/deletions and mismatches. The binary alphabet having a size of 2 and that of DNA having a size of 4 does not require the use of different algorithms if the element-wise comparison results in either "match" or "mismatch", and a mismatch is penalized for. Check out the Needleman–Wunsch algorithm, which is based on dynamic programming.

Some DNA/protein sequence alignment algorithms such as MAFFT use Fast Fourier Transform (FFT) for accelerated cross-correlation of residue properties to approximate match calculations.