Recommendation sought for basic string difference algorithm

Question

Hello,

I'm looking for an algorithm that takes as arguments two strings, source and destination, and returns the steps required to transform the source string to the destination. Something that takes Levenshtein distance one step farther.

E.g.,

Input: source "abc", dest "abbc"
Output: insert 'b' at position 1 in source

Input: source "abc", dest "ac"
Output: delete 'b' at position 1 in source

Thanks very much.

Answer 1

Take a look at the diff algorithms on Wikipedia.

Answer 2

You might try going through first and lining up all the letters in pairs. After you've paired as many as possible, the inserts and deletes should be obvious.

abcde
| /|
acbdd

So you remove the b & e and add a b & d

Remember the lines can't cross.

Answer 3

I would try to find a way to send it to an existing well-tested diff utility and use the results of that diff, e.g. diff -e or diff -n.

Answer 4

Just use the algorithm as shown on wikipedia, understand it and make the modifications that are necessary. I does solve your problem, you probably just didn't know it, and didn't record your answer along the way.