在C＃中查找子数组的第一个出现/起始索引
给定两个数组作为参数（x和y）并找到x中第一次出现y的起始索引。 我想知道最简单或最快的实现是什么。
例：
when x = {1,2,4,2,3,4,5,6} y = {2,3} result starting index should be 3 更新：由于我的代码错误，我将其从问题中删除。
这是一个简单（但相当有效）的实现，它可以找到数组的所有出现，而不仅仅是第一个：
static class ArrayExtensions { public static IEnumerable StartingIndex(this int[] x, int[] y) { IEnumerable 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();
这将找不到所有匹配然后返回第一个匹配，只搜索直到第一个匹配，然后返回它。
最简单的写？
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; }
最简单的方法可能就是：
public static class ArrayExtensions { private static bool isMatch(int[] x, int[] y, int index) { for (int j = 0; j < y.Length; ++j) if (x[j + index] != y[j]) return false; return true; } public static int IndexOf(this int[] x, int[] y) { for (int i = 0; i < x.Length - y.Length + 1; ++i) if (isMatch(x, y, i)) return i; return -1; } }
但它绝对不是最快的方式。
在这种情况下，“最简单”和“最快”是对立的，此外，为了描述快速算法，我们需要了解有关源数组和搜索数组如何相互关联的许多内容。
这与在字符串中查找子字符串基本相同。 假设你在“快速的棕色狐狸跳过懒狗”中寻找“狐狸”。 在这种情况下，天真的字符串匹配算法非常好。 如果你在“banananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananan 。 基本上，朴素算法是O（nm），其中n和m是源和搜索字符串的长度。 有O（n + m）算法，但它们要复杂得多。
您能告诉我们您正在搜索的数据的更多信息吗？ 它有多大，多么多余，搜索arrays有多长，不匹配的可能性是多少？
这是基于Mark Gravell的答案，但我将其设为通用，并添加了一些简单的边界检查，以防止exception被抛出
private static bool IsSubArrayEqual(T[] source, T[] compare, int start) where T:IEquatable { if (compare.Length > source.Length - start) { //If the compare string is shorter than the test area it is not a match. return false; } for (int i = 0; i < compare.Length; i++) { if (source[start++].Equals(compare[i]) == false) return false; } return true; }
可以通过实施Boyer-Moore进一步改进，但对于短模式，它可以正常工作。
我发现以下几行更直观，但这可能是一种品味问题。
public static class ArrayExtensions { public static int StartingIndex(this int[] x, int[] y) { var xIndex = 0; while(xIndex < x.length) { var found = xIndex; var yIndex = 0; while(yIndex < y.length && xIndex < x.length && x[xIndex] == y[yIndex]) { xIndex++; yIndex++; } if(yIndex == y.length-1) { return found; } xIndex = found + 1; } return -1; } }
此代码还解决了我认为您的实现在x = {3,3,7}，y = {3,7}等情况下可能遇到的问题。 我认为你的代码会发生什么，它匹配第一个数字，然后在第二个数字上重置自己，但在第三个数字上再次开始匹配，而不是在它开始匹配之后回到索引。 可能会遗漏一些东西，但它绝对值得考虑，应该可以在代码中轻松修复。
//this is the best in C# //bool contains(array,subarray) // when find (subarray[0]) // while subarray[next] IS OK // subarray.end then Return True public static bool ContainSubArray(T[] findIn, out int found_index, params T[]toFind) { found_index = -1; if (toFind.Length < findIn.Length) { int index = 0; Func NextOk = (i) => { if(index < findIn.Length-1) return findIn[++index].Equals(toFind[i]); return false; }; //---------- int n=0; for (; index < findIn.Length; index++) { if (findIn[index].Equals(toFind[0])) { found_index=index;n=1; while (n < toFind.Length && NextOk(n)) n++; } if (n == toFind.Length) { return true; } } } return false; }