c# - linq 另一个列表的有序子集

Question

SO 上有很多关于查找一个列表是否是另一个列表的子集的问题。

即bool isSubset = !t2.Except(t1).Any();

我好像找不到一个能说明顺序的

如给定的序列:

1,1,2,5,8,1,9,1,2

子序列...

2,5,8,1,9 真

1,2,5,8,1 真

5,2,1 错误

1,2,5,1,8 错误

1,1,2 真

1,1,1,2 错误

Answer 1

顺序重要的列表是字符串 概念的概括。因此，您想使用子串查找算法。

有多种可能性，但 Knuth–Morris–Pratt 是一个不错的选择。它有一些初始的 Θ(m) 开销，其中 m 是所寻找的子列表的长度，然后在 Θ(n) 中找到，其中 n 是到所寻找的子列表的距离，如果不存在则为整个列表的长度.这胜过简单的逐项比较，即 Θ((n-m+1) m):

public static class ListSearching
{
  public static bool Contains<T>(this IList<T> haystack, IList<T> needle)
  {
    return Contains(haystack, needle, null);
  }
  public static bool Contains<T>(this IList<T> haystack, IList<T> needle, IEqualityComparer<T> cmp)
  {
    return haystack.IndexOf(needle, cmp) != -1;
  }
  public static int IndexOf<T>(this IList<T> haystack, IList<T> needle)
  {
    return IndexOf(haystack, needle, null);
  }
  public static int IndexOf<T>(this IList<T> haystack, IList<T> needle, IEqualityComparer<T> cmp)
  {
    if(haystack == null || needle == null)
      throw new ArgumentNullException();
    int needleCount = needle.Count;
    if(needleCount == 0)
      return 0;//empty lists are everywhere!
    if(cmp == null)
      cmp = EqualityComparer<T>.Default;
    int count = haystack.Count;
    if(needleCount == 1)//can't beat just spinning through for it
    {
      T item = needle[0];
      for(int idx = 0; idx != count; ++idx)
        if(cmp.Equals(haystack[idx], item))
          return idx;
      return -1;
    }
    int m = 0;
    int i = 0;
    int[] table = KMPTable(needle, cmp);
    while(m + i < count)
    {
      if(cmp.Equals(needle[i], haystack[m + i]))
      {
        if(i == needleCount - 1)
          return m == needleCount ? -1 : m;//match -1 = failure to find conventional in .NET
        ++i;
      }
      else
      {
        m = m + i - table[i];
        i = table[i] > -1 ? table[i] : 0;
      }
    }
    return -1;
  }
  private static int[] KMPTable<T>(IList<T> sought, IEqualityComparer<T> cmp)
  {
    int[] table = new int[sought.Count];
    int pos = 2;
    int cnd = 0;
    table[0] = -1;
    table[1] = 0;
    while(pos < table.Length)
      if(cmp.Equals(sought[pos - 1], sought[cnd]))
        table[pos++] = ++cnd;
      else if(cnd > 0)
        cnd = table[cnd];
      else
        table[pos++] = 0;
    return table;
  }
}

测试这个:

var list = new[]{ 1, 1, 2, 5, 8, 1, 9, 1, 2 };
Console.WriteLine(list.Contains(new[]{2,5,8,1,9})); // True
Console.WriteLine(list.Contains(new[]{1,2,5,8,1})); // True
Console.WriteLine(list.Contains(new[]{5,2,1}));     // False
Console.WriteLine(list.Contains(new[]{1,2,5,1,8})); // False
Console.WriteLine(list.Contains(new[]{1,1,2}));     // True
Console.WriteLine(list.Contains(new[]{1,1,1,2}));   // False