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

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} добавлено "пить свежую воду" и "1014 *

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

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

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

Прежде чем изобретать велосипед - есть ли решение в свободном доступе?

Answer 1

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

Часть 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: Выделение слов.

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

Answer 2

Вы в основном пытаетесь реализовать эквивалент diff . Как объяснено на странице википедии, он использует алгоритм самая длинная общая подпоследовательность *1004*.