在较长的顺序查找子 [英] Finding a subsequence in longer sequence

问题描述

我需要找到其他大型顺序的顺序，例如， {1,3,2,3} 出现在 {1 ，3,2,3,4,3} 和 {5,1,3,2,3} 。有没有什么办法与 IEnumerable的快快行动吧或别的？

I need to find a sequence in other large sequence, for example, {1,3,2,3} is present in {1,3,2,3,4,3} and {5,1,3,2,3}. Is there any way to do it quickly with IEnumerable or with something else?

推荐答案

此方法会找到一个父序列中的一个子的任何类型，可以通过进行比较，等于（）：

This method will find a subsequence within a parent sequence, of any type that can be compared via Equals():

public static bool ContainsSubequence<T>(this IEnumerable<T> parent, IEnumerable<T> target)
{
    bool foundOneMatch = false;
    using (IEnumerator<T> parentEnum = parent.GetEnumerator())
    {
        using (IEnumerator<T> targetEnum = target.GetEnumerator())
        {
            // Get the first target instance; empty sequences are trivially contained
            if (!targetEnum.MoveNext())
                return true;

            while (parentEnum.MoveNext())
            {
                if (targetEnum.Current.Equals(parentEnum.Current))
                {
                    // Match, so move the target enum forward
                    foundOneMatch = true;
                    if (!targetEnum.MoveNext())
                    {
                        // We went through the entire target, so we have a match
                        return true;
                    }
                }
                else if (foundOneMatch)
                {
                    return false;
                }
            }

            return false;
        }
    }
}

您可以使用它像这样

bool match = new[] {1, 2, 3}.ContainsSubsequence(new[] {1, 2}); // match == true
match = new[] {1, 2, 3}.ContainsSubsequence(new[] {1, 3}); // match == false

请注意，它假定靶序列不具有 。空元素

Note that it assumes the target sequence has no null elements.

更新：谢谢你的upvotes，每个人，但实际上是一个错误在上面的代码！如果发现部分匹配，但不会变成一个完整的比赛，该过程的结束的，而不是复位时（如应用到一些东西，显然是incorrected { 1，2，1，2，3} .ContainsSubsequence（{1，2，3}））。

Update: Thanks for the upvotes, everyone, but there is actually a bug in the above code! If a partial match is found, but then doesn't turn into a full match, the process is ended, rather than reset (which is obviously incorrected when applied to something like {1, 2, 1, 2, 3}.ContainsSubsequence({1, 2, 3})).

上面的代码的作品真的以及为子序列的更通用的定义（即contiguousness不需要），但为了处理复位（其最 IEnumerators 不支持）的靶序列需要被列举了面前。这导致下面的代码：

The above code works really well for the more common definition of subsequence (i.e. contiguousness is not required) but in order to handle resetting (which most IEnumerators do not support) the target sequence needs to be enumerated up front. That leads to the following code:

public static bool ContainsSubequence<T>(this IEnumerable<T> parent, IEnumerable<T> target)
{
    bool foundOneMatch = false;
    var enumeratedTarget = target.ToList();
    int enumPos = 0;

    using (IEnumerator<T> parentEnum = parent.GetEnumerator())
    {
        while (parentEnum.MoveNext())
        {
            if (enumeratedTarget[enumPos].Equals(parentEnum.Current))
            {
                // Match, so move the target enum forward
                foundOneMatch = true;
                if (enumPos == enumeratedTarget.Count - 1)
                {
                    // We went through the entire target, so we have a match
                    return true;
                }

                enumPos++;
            }
            else if (foundOneMatch)
            {
                foundOneMatch = false;
                enumPos = 0;

                if (enumeratedTarget[enumPos].Equals(parentEnum.Current))
                {
                    foundOneMatch = true;
                    enumPos++;
                }
            }
        }

        return false;
    }
}

这代码没有任何错误，但韩元'吨大（或无限）序列的工作。

This code doesn't have any bugs, but won't work well for large (or infinite) sequences.

这篇关于在较长的顺序查找子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！