在C#中查找子数组的第一个出现/起始索引

Question

给定两个数组作为参数(x和y)并找到x中第一次出现y的起始索引.我想知道最简单或最快的实现是什么.

例:

when x = {1,2,4,2,3,4,5,6}
     y =       {2,3}
result
     starting index should be 3

更新:由于我的代码错误,我将其从问题中删除.

Answer 1

最简单的写？

    return (from i in Enumerable.Range(0, 1 + x.Length - y.Length)
            where x.Skip(i).Take(y.Length).SequenceEqual(y)
            select (int?)i).FirstOrDefault().GetValueOrDefault(-1);

当然不是那么有效......有点像它:

private static bool IsSubArrayEqual(int[] x, int[] y, int start) {
    for (int i = 0; i < y.Length; i++) {
        if (x[start++] != y[i]) return false;
    }
    return true;
}
public static int StartingIndex(this int[] x, int[] y) {
    int max = 1 + x.Length - y.Length;
    for(int i = 0 ; i < max ; i++) {
        if(IsSubArrayEqual(x,y,i)) return i;
    }
    return -1;
}

Answer 2

这是一个简单(但相当有效)的实现,它可以找到数组的所有出现,而不仅仅是第一个:

static class ArrayExtensions {

  public static IEnumerable<int> StartingIndex(this int[] x, int[] y) {
    IEnumerable<int> index = Enumerable.Range(0, x.Length - y.Length + 1);
    for (int i = 0; i < y.Length; i++) {
      index = index.Where(n => x[n + i] == y[i]).ToArray();
    }
    return index;
  }

}

例:

int[] x = { 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4 };
int[] y = { 2, 3 };
foreach (int i in x.StartingIndex(y)) {
  Console.WriteLine(i);
}

输出:

1
5
9

该方法首先遍历x数组以查找数组中第一个项的所有出现,并将这些项y的索引放在index数组中.然后继续通过检查哪些匹配y数组中的第二项来减少匹配.y检查index数组中的所有项目时,该数组仅包含完整匹配项.

编辑:
另一种实现方法是ToArray从循环中的语句中删除调用,使其成为:

index = index.Where(n => x[n + i] == y[i]);

这将完全改变方法的工作方式.它不是逐级循环遍历项目,而是返回具有嵌套表达式的枚举器,将搜索推迟到迭代枚举器的时间.这意味着如果你想要,你只能获得第一场比赛:

int index = x.StartingIndex(y).First();

这将找不到所有匹配,然后返回第一个匹配,只搜索直到第一个匹配,然后返回它.