Как определить дельта перемен между двумя строками?

Question

Я должен реализовать алгоритм, который принимает в качестве входных данных две строки и возвращает массив, содержащий диапазоны изменений подстроки.

Скажем, диапазон определяется как

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

Пример:

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

Изменения:

• {7,9} "иногда" изменено на {7, 6} «всегда»
• {26,0} добавлено «выпить пресную воду» и «

Мне нужен массив, который содержит подстроки, сгруппированные по изменениям. В данном примере это будет выглядеть следующим образом:

• "Моя кошка"
• "всегда"
• "любит"
• "пить свежую воду, и"
• "едят рыбу."

Цель состоит в том, чтобы выделить эти изменения в существующей строке, для которой я должен разбить эту строку на подстроки на основе изменений.

Перед тем как изобретать колесо - есть ли решение в общественном достоянии?

Answer 1

Вы в основном пытаетесь реализовать эквивалент diff. Как поясняется на странице wikipedia, он использует алгоритм longest common subsequence problem.

Answer 2

Мы разделили задачу на две части.

Часть 1: Поиск различий.

Вы можете сделать это, используя следующий код,

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); 

Часть 2: Выделение слова.

Узнав слова, легко выделить.