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.

Answer 2

We split the task into two parts.

Part 1 : Finding the differences.

You can do this using the following code,

NSString *string1 = @"My cat sometimes likes to eat fish.";
 NSString * string2 = @"My cat always likes to drink fresh water, and eat fish.";
NSMutableSet *set1 = [NSMutableSet setWithArray:[string1 componentsSeparatedByString:@" "]];
NSMutableSet *set2 = [NSMutableSet setWithArray:[string2 componentsSeparatedByString:@" "]];
[set2 minusSet:set1];
NSLog(@"%@",set2);

Part 2: Highlighting the words.

Once after knowing the words it is easy to highlight.