以更长的顺序查找子序列

我需要找到其他大序列的序列，例如， {1,3,2,3,4,3}和{5,1,3,2,3}存在{1,3,2,3,4,3} {5,1,3,2,3} 。 有没有办法快速使用IEnumerable或其他东西？

Answer 1

此方法将在父序列中找到可通过Equals()进行比较的任何类型的子序列：

 public static bool ContainsSubequence(this IEnumerable parent, IEnumerable target) { bool foundOneMatch = false; using (IEnumerator parentEnum = parent.GetEnumerator()) { using (IEnumerator 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 

请注意，它假定目标序列没有null元素。

更新 ：感谢大家的赞成，但上面的代码实际上有一个错误 ！ 如果找到了部分匹配，但是没有变成完全匹配，则该过程结束 ，而不是重置（当应用于{1, 2, 1, 2, 3}.ContainsSubsequence({1, 2, 3})时，这显然是{1, 2, 1, 2, 3}.ContainsSubsequence({1, 2, 3}) ）。

上面的代码非常适用于子序列的更常见定义（即不需要连续性），但是为了处理重置（大多数IEnumerators不支持），需要预先枚举目标序列。 这导致以下代码：

 public static bool ContainsSubequence(this IEnumerable parent, IEnumerable target) { bool foundOneMatch = false; var enumeratedTarget = target.ToList(); int enumPos = 0; using (IEnumerator 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; } } 

此代码没有任何错误，但不适用于大型（或无限）序列。

Answer 2

与@ dlev类似，但这也处理{1,1,1,2}.ContainsSubsequence({1,1,2})

 public static bool ContainsSubsequence(this IEnumerable parent, IEnumerable target) { var pattern = target.ToArray(); var source = new LinkedList(); foreach (var element in parent) { source.AddLast(element); if(source.Count == pattern.Length) { if(source.SequenceEqual(pattern)) return true; source.RemoveFirst(); } } return false; } 

Answer 3

你可以尝试这样的东西来帮助你入门。 将此列表转换为字符串后，您可以使用子字符串找到序列：

 if (String.Join(",", numericList.ConvertAll(x => x.ToString()).ToArray()) { //get sequence } 

Answer 4

如果您正在处理简单的可序列化类型，那么如果将数组转换为字符串，则可以非常轻松地执行此操作：

 public static bool ContainsList(this List containingList, List containedList) { string strContaining = "," + string.Join(",", containingList) + ","; string strContained = "," + string.Join(",", containedList) + ","; return strContaining.Contains(strContained); } 

请注意，这是一种扩展方法，因此您可以将其称为：

 if (bigList.ContainsList(smallList)) { ... } 

Answer 5

这对我有用

 var a1 = new List { 1, 2, 3, 4, 5 }; var a2 = new List { 2, 3, 4 }; int index = -1; bool res = a2.All( x => index != -1 ? (++index == a1.IndexOf(x)) : ((index = a1.IndexOf(x)) != -1) ); 

Answer 6

此函数使用一些LINQ检查List parent是否包含List target ：

  public static bool ContainsSequence(this List parent, List target) { for (int fromElement = parent.IndexOf(target.First()); (fromElement != -1) && (fromElement <= parent.Count - target.Count); fromElement = parent.FindIndex(fromElement + 1, p => p.Equals(target.First()))) { var comparedSequence = parent.Skip(fromElement).Take(target.Count); if (comparedSequence.SequenceEqual(target)) return true; } return false; }