My first thought was that the problem is similar to what you might do in bioinformatics, as mentioned by Anonymous earlier. Although there are are likely significant differences between bitstrings and character strings that I can't help you with, I was listening to Natural Language Processing lectures on Coursera and the Edit Distance lectures attacked the problem with Dynamic Programming. Maybe that helps you with the coding strategy?

Sometimes I can think of 6 impossible LDAP attributes before breakfast.

In reply to Re: [OT] The interesting problem of comparing bit-strings. by Ea
in thread [OT] The interesting problem of comparing bit-strings. by BrowserUk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":