How to determine the delta of changes between two lines?

Question

I need to implement an algorithm that takes two strings as input and returns an array containing the ranges of the substring 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."; 

Changes:

• {7.9} "sometimes" changed to {7.6} "always"
• {26.0} added "drink fresh water" and "

I need an array that contains substrings grouped by change. In this example, it will look like this:

• "My cat"
• "is always"
• "like"
• "drink fresh water and
• "to eat fish".

The goal is to highlight these changes in an existing line, for which I have to split this line into substrings based on the changes.

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

Answer 1

Basically you are trying to implement the equivalent of diff . As explained on the wikipedia page, it uses an algorithm with the longest common subsequence problem .

Answer 2

We divided the task into two parts.

Part 1: Search for 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 words.

Once you recognize the words, they are easy to distinguish.