给定两个数组作为参数（x 和 y），并找到 y 在 x 中第一次出现的起始索引。我想知道最简单或最快的实现是什么。
示例：
when x = {1,2,4,2,3,4,5,6}
y = {2,3}
result
starting index should be 3
更新：由于我的代码是错误的，所以我将其从问题中删除了。
最简单的写法？
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;
}
这是一个简单（但相当有效）的实现，可以查找数组中所有出现的地方，而不仅仅是第一个：
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
该方法首先循环遍历
xyindexyyindex编辑：
另一种实现是从循环中的语句中删除
ToArrayindex = index.Where(n => x[n + i] == y[i]);
这将完全改变该方法的工作方式。它不是逐级循环遍历项目，而是返回一个带有嵌套表达式的枚举器，将搜索推迟到迭代枚举器时。这意味着如果您愿意，您只能获得第一场比赛：
int index = x.StartingIndex(y).First();
这不会找到所有匹配项，然后返回第一个，它只会搜索直到找到第一个匹配项，然后返回它。
最简单的方法可能是这样的：
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;
}
}
但这绝对不是最快的方法。
这是基于 Mark Gravell 的答案，但我将其变得通用，并添加了一些简单的边界检查以防止抛出异常
private static bool IsSubArrayEqual<T>(T[] source, T[] compare, int start) where T:IEquatable<T>
{
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进一步改进，但对于较短的模式，它工作得很好。
在这种情况下，“最简单”和“最快”是相反的，此外，为了描述快速算法，我们需要了解很多关于源数组和搜索数组如何相互关联的事情。
这本质上与在字符串中查找子字符串是相同的问题。 假设您正在“the Quick Brown Fox Jumps Over the Lazy Dog”中查找“Fox”。 在这种情况下，朴素的字符串匹配算法非常好。 如果您要在“banananananabananabananabananabananananbananana...”形式的百万字符字符串中搜索“banananananananananananananana”，那么简单的子字符串匹配算法是terrible——通过使用更复杂和复杂的字符串可以获得更快的结果匹配算法。基本上，简单的算法是 O(nm)，其中 n 和 m 是源字符串和搜索字符串的长度。有 O(n+m) 种算法，但它们要复杂得多。
您能告诉我们更多有关您正在搜索的数据的信息吗？ 它有多大，冗余有多大，搜索数组有多长，以及错误匹配的可能性有多大？
我发现以下内容更直观，但这可能是一个品味问题。
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>(T[] findIn, out int found_index,
params T[]toFind)
{
found_index = -1;
if (toFind.Length < findIn.Length)
{
int index = 0;
Func<int, bool> 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;
}
using System;
using System.Linq;
public class Test
{
public static void Main()
{
int[] x = {1,2,4,2,3,4,5,6};
int[] y = {2,3};
int? index = null;
for(int i=0; i<x.Length; ++i)
{
if (y.SequenceEqual(x.Skip(i).Take(y.Length)))
{
index = i;
break;
}
}
Console.WriteLine($"{index}");
}
}
3
public class Test
{
static void Main()
{
int[] x = { 1, 2, 4, 2, 3, 4, 5, 6 };
int[] y = { 2, 3 };
int index = new ReadOnlySpan<int>(x).IndexOf(y);
if (index < 0)
Console.WriteLine("Subarray not found");
else
Console.WriteLine("Subarray found at index " + index);
}
}
public static bool Includes<T>(this IReadOnlyList<T> haystack, IReadOnlyList<T> needle, int start = 0)
{
var h = start;
var n = 0;
var res = false;
while (h < haystack.Count && n < needle.Count)
{
res = haystack[h].Equals(needle[n]);
if (res)
{
h++;
n++;
}
else
{
h = ++start;
n = 0;
}
}
return res && n == needle.Count;
}