c# - c#提取非重叠排序范围的最有效方法

Question

为了突出显示单个字符串中的多个搜索文本元素，我有一个例程计算要在字符串本身中突出显示的范围。

例如，如果我his+is在字符串“这是我的错误测试”中搜索字符串，我会得到高亮显示的范围[1,3]、[2,3]、[5,6]和[12,13]。

所以我想要的结果是[1,3],[5,6]和[12,13]。

有没有从上面的列表中提取非重叠范围的一般方法？或者事件更好，是否有特定于字符串的方法来获取这些？

Answer 1

1. 按开始索引对范围进行排序。（您的程序很可能已经这样做了）
2. 选择第一个范围
3. 跳过在当前选定范围结束之前开始的所有范围（继续检查下一个，直到找到在当前选定范围结束之后开始的范围）
4. 选择新范围
5. 转到 3

如果您想基于文本进行操作，则取决于您可能的搜索模式（正则表达式？）的复杂性。如果您指定这一点，我很乐意为您提供帮助。

Answer 2

你对高效的理解是什么？快速地？最少的内存使用？可维护的代码？

有很多方法可以解决这个问题，其中一些可能需要看似很多代码，但也许这还不错。例如，考虑以下方法：

public struct Interval<T> where T: IComparable<T>
{
    public T LowerBound { get; }
    public T UpperBound { get; }

    public Interval(T lowerBound, T upperBound)
    {
        Debug.Assert(upperBound.CompareTo(lowerBound) > 0);
        LowerBound = lowerBound;
        UpperBound = upperBound;
    }

    public static bool AreOverlapping(Interval<T> first, Interval<T> second) => 
        first.UpperBound.CompareTo(second.LowerBound) > 0 &&
        second.UpperBound.CompareTo(first.LowerBound) > 0;

    public static Interval<T> Union(Interval<T> first, Interval<T> second)
    {
        Debug.Assert(AreOverlapping(first, second));
        return new Interval<T>(Min(first.LowerBound, second.LowerBound),
                               Max(first.UpperBound, second.UpperBound));
    }

    public override string ToString() => $"[{LowerBound}, {UpperBound}]";

    private static T Min(T t1, T t2)
    {
        if (t1.CompareTo(t2) <= 0)
            return t1;

        return t2;
    }

    private static T Max(T t1, T t2)
    {
        if (t1.CompareTo(t2) >= 0)
            return t1;

        return t2;
    }
}

现在，我们提取非重叠间隔的方法是：

public static IEnumerable<Interval<T>> GetOverlappingIntervals<T>(this IEnumerable<Interval<T>> intervals)
    where T : IComparable<T>
{
    var stack = new Stack<Interval<T>>();

    foreach (var interval in intervals.OrderBy(i => i.LowerBound))
    {
        if (stack.Count == 0)
        {
            stack.Push(interval);
        }
        else
        {
            var previous = stack.Peek();

            if (Interval<T>.AreOverlapping(interval, previous))
            {
                stack.Pop();
                stack.Push(Interval<T>.Union(interval, previous));
            }
            else
            {
                stack.Push(interval);
            }
        }
    }

    return stack;
}

请注意，此解决方案不会执行相邻间隔的并集，不确定这是否是您想要的。

这个解决方案是否可以维护？是的，代码几乎是不言自明的。它是最有效的吗？好吧，可能不是，但谁在乎它是否足够“高效”并满足您的性能目标。如果没有，请开始优化它。