How to identify deltas of changes between two strings?

Question

I have to implement an algorithm which takes as input two strings, and returns an array containing substring ranges of changes.

Say, a range is defined as

typedef struct _NSRange {
    NSUInteger location; // Where the affected substring begins
    NSUInteger length; // How long the affected substring is
} NSRange;

Example:

string1 = "My cat sometimes likes to eat fish.";
string 2 = "My cat always likes to drink fresh water, and eat fish.";

The changes are:

• {7,9} "sometimes" changed to {7,6} "always"
• {26,0} added "drink fresh water, and "

I need an array which contains substrings grouped by changes. In this example it would look like this:

• "My cat "
• "always"
• " likes to "
• "drink fresh water, and"
• " eat fish."

The goal is to highlight those changes in an existing string, for which I must split that string into substrings based on changes.

Before reinventing the wheel - is there a solution in the public domain?

Answer 1

You are basically trying to implement the equivalent of diff. As explained in the wikipedia page, it uses the longest common subsequence problem algorithm.