2 ms·
> Eg. what's the edit distance between these two strings? > > AAAA BBBB > > Traditionally, it would be 4, but it's unclear if you > allow only inser
by wolfgke 11y ago
> Eg. what's the edit distance between these two strings?
>
> AAAA BBBB
>
> Traditionally, it would be 4, but it's unclear if you
> allow only inserts and deletions.
It is >= 8, since you surely have to remove 4 As and insert 4 Bs. Since these 8 transformations indeed transform AAAA into BBBB, it is exactly 8.
It is very easy to generalize the Wagner-Fisher algorithm (https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorit...) to this "simpler" variant of edit distance, but this algorithm will still have a (worst-case) runtime of O(m*n), where m, n are the lengths of the two strings.
Of course, the question remains: Is there a (worst-case) faster algorithm?
- jongraehl 11y agoDon't know, but you still end up aligning common subsequences (advanced monotonically in both seqs) and you still have the same order-of-computing-cells allowed in the standard m*n dynamic program. Your restricted problem is basically asking for the standard unix line-diff.