c# - 使用 Linq 在 IEnumerable 中查找序列

Question

在 IEnumerable<T> 中查找序列的最有效方法是什么？使用 LINQ

我希望能够创建一个允许以下调用的扩展方法:

int startIndex = largeSequence.FindSequence(subSequence)

匹配必须是相邻的并且是有序的。

Answer 1

下面是一个在序列中查找子序列的算法的实现。我将方法称为 IndexOfSequence，因为它使意图更加明确并且类似于现有的 IndexOf 方法:

public static class ExtensionMethods
{
    public static int IndexOfSequence<T>(this IEnumerable<T> source, IEnumerable<T> sequence)
    {
        return source.IndexOfSequence(sequence, EqualityComparer<T>.Default);
    }

    public static int IndexOfSequence<T>(this IEnumerable<T> source, IEnumerable<T> sequence, IEqualityComparer<T> comparer)
    {
        var seq = sequence.ToArray();

        int p = 0; // current position in source sequence
        int i = 0; // current position in searched sequence
        var prospects = new List<int>(); // list of prospective matches
        foreach (var item in source)
        {
            // Remove bad prospective matches
            prospects.RemoveAll(k => !comparer.Equals(item, seq[p - k]));

            // Is it the start of a prospective match ?
            if (comparer.Equals(item, seq[0]))
            {
                prospects.Add(p);
            }

            // Does current character continues partial match ?
            if (comparer.Equals(item, seq[i]))
            {
                i++;
                // Do we have a complete match ?
                if (i == seq.Length)
                {
                    // Bingo !
                    return p - seq.Length + 1;
                }
            }
            else // Mismatch
            {
                // Do we have prospective matches to fall back to ?
                if (prospects.Count > 0)
                {
                    // Yes, use the first one
                    int k = prospects[0];
                    i = p - k + 1;
                }
                else
                {
                    // No, start from beginning of searched sequence
                    i = 0;
                }
            }
            p++;
        }
        // No match
        return -1;
    }
}

我没有完全测试它，所以它可能仍然包含错误。我只是对众所周知的角落案例进行了一些测试，以确保我没有掉入明显的陷阱。到目前为止似乎工作正常......

我认为复杂度接近于 O(n)，但我不是 Big O 符号的专家所以我可能是错的......至少它只枚举源序列一次，而不会返回，所以它应该相当有效。