c# - 根据一组重叠范围将字符串拆分为多个范围

Question

我需要根据一组范围值将一个字符串拆分为多个子字符串，每个子字符串都标记有一组适用范围。结果子字符串集合中不应有重叠，并且与集合中任何范围不匹配的子字符串仍需要包含在结果中。

目前，我遍历整个字符串以找到每个字符的匹配范围，然后遍历该迭代的结果以基于连续的匹配范围集构建每个子字符串。不过，我确信有一种更有效的方法可以做到这一点。

此应用程序是用 C# 编写的，但也接受用于解决此问题的算法的文本描述。

例子

令字符串为:

Scelerisque suspendisse congue habitant scelerisque sociis placerat a himenaeos diam nunc vestibulum nec ultrices nisl himenaeos viverra mus hac.

将范围指定为开始和结束索引(包括):

1. (12,50) - 匹配“suspendisse congue habitant scelerisque”
2. (24,29) - 匹配“congue”
3. (59,88) - 匹配“placerat a himenaeos diam nunc”
4. (80,103) - 匹配“diam nunc vestibulum nec”
5. (114,127) - 匹配“nisl himenaeos”

结果应该是:

1. 范围(0,11)，子字符串“Scelerisque”，匹配范围[]
2. 范围(12,23)，子字符串“suspendisse”，匹配范围[1]
3. 范围 (24,29)，子字符串“congue”，匹配范围 [1,2]
4. range (30,50)，子字符串“habitant scelerisque”，匹配范围[1]
5. 范围(51,58)，子字符串“sociis”，匹配范围[]
6. range (59,79)，子串“placerat a himenaeos”，匹配范围[3]
7. 范围 (80,88)，子字符串“diam nunc”，匹配范围 [3,4]
8. range (89,103)，子串“vestibulum nec”，匹配范围[4]
9. 范围(104,113)，子字符串“ultrices”，匹配范围[]
10. 范围 (114,127)，子字符串“nisl himenaeos”，匹配范围 [5]
11. 范围 (128,144)，子字符串“viverra mus hac.”，匹配范围 []

更多信息

范围永远不会是零长度。拆分操作的结果也不应包含任何零长度子字符串。

除了简单的重叠，多个范围可以有相同的起始索引或结束索引。这在上面的示例中没有演示。

Answer 1

• 将范围拆分为事件(索引、类型、范围):1. (12,50) => (12, start, 1) and (50, end, 1)
• 对它们进行排序
• 初始化一组空整数，currentIndex = 0
• 迭代每个事件
• 如果事件是一个开始，插入结果(currentIndex，event.index - 1)，匹配范围= set.toArray()。添加 event.range 来设置。设置 currentIndex = event.index
• 如果事件结束，则插入结果(currentIndex、event.index)，匹配 ranges = set.toArray()。从集合中删除 event.range。设置 currentIndex = event.index + 1
• 全部迭代完成后，补上缺失的结果:(currentIndex, string.length), matches []

这在假设事件具有唯一索引的情况下有效。需要一些修改来处理 [(12,50), (12,40), (15, 50)] 之类的事情。