4

我必须实现一个算法，它将两个字符串作为输入，并返回一个包含子字符串变化范围的数组。

比如说，一个范围被定义为

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} 添加了“喝淡水，并且”

我需要一个包含按更改分组的子字符串的数组。在此示例中，它看起来像这样：

  • “我的猫 ”
  • “总是”
  • “ 喜欢 ”
  • “喝淡水，然后”
  • “ 吃鱼。”

目标是突出现有字符串中的这些更改，为此我必须根据更改将该字符串拆分为子字符串。

在重新发明轮子之前 - 公共领域有解决方案吗？

4

2 回答 2

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 部分：突出显示单词。

一旦知道单词后，很容易突出显示。

于 2012-02-29T16:37:09.683 回答
0

您基本上是在尝试实现等效的diff。正如维基百科页面中所解释的，它使用最长的公共子序列问题算法。

于 2012-02-29T16:27:23.403 回答