发现C＃中的第一次出现/开始子阵列的索引 [英] Find the first occurrence/starting index of the sub-array in C#

问题描述

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

Given two arrays as parameters (x and y) and find the starting index where the first occurrence of y in x. I am wondering what the simplest or the fastest implementation would be.

例如：

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

更新：由于我的code是错了，我删除它的问题。

Update: Since my code is wrong I removed it from the question.

推荐答案

下面是一个简单的（但相当有效）实现，发现该阵列的所有出现，不只是第一个：

Here is a simple (yet fairly efficient) implementation that finds all occurances of the array, not just the first one:

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 阵列来查找是数组的第一个项目的所有出现，并把那些在首页数组的索引。它接着通过检查哪些那些在是阵列也匹配第二个项目，以减少比赛。当在Ÿ所有项目阵列被选中，首页数组只包含一个完整的比赛。

The method first loops through the x array to find all occurances of the first item in the y array, and place the index of those in the index array. Then it goes on to reduce the matches by checking which of those also match the second item in the y array. When all items in the y array is checked, the index array contains only the full matches.

编辑：结果
另一种实现是去除在循环语句中的的ToArray 调用，使得它只是：

An alternative implementation would be to remove the ToArray call from the statement in the loop, making it just:

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

这将完全改变的方法是如何工作的。相反，通过水平的项目级别的循环，它会返回嵌套前pressions一个枚举，推迟搜索到的时候，枚举数迭代。这意味着，如果你想，你可以得到的只是第一场比赛：

This would totally change how the method works. Instead of looping through the items level by level, it would return an enumerator with nested expressions, deferring the search to the time when the enumerator was iterated. That means that you could get only the first match if you wanted:

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

这也不会找到所有的匹配，然后返回第一个，它只是搜索，直到第一个被发现，然后返回。

This would not find all matches and then return the first, it would just search until the first was found and then return it.

这篇关于发现C＃中的第一次出现/开始子阵列的索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！