c# - 在类似于 String IndexOf() 的更大 byte[] 中寻找 byte[]？

Question

假设我有一个大的 byte[]，我不仅要查看较大的数组中是否还有较小的 byte[] .例如:

byte[] large = new byte[100];
for (byte i = 0; i < 100; i++) {
    large[i] = i;
}
byte[] small = new byte[] { 23, 24, 25 };

int loc = large.IndexOf(small); // this is what I want to write

我想我问的是在更大的序列中寻找任何类型(原始或其他)的序列。

我依稀记得在字符串中读过有关此的特定方法，但我不记得算法的名称。我可以很容易地写一些方法来做到这一点，但我知道有一个很好的解决方案，而且它就在我的舌尖上。如果有一些 .Net 方法可以做到这一点，我也会采用它(尽管出于教育目的，我仍然很欣赏搜索算法的名称)。

Answer 1

您可以使用 LINQ 来完成，如下所示:

var res = Enumerable.Range(0, large.Length-1)
    .Cast<int?>()
    .FirstOrDefault(n => large.Skip(n.Value).Take(small.Length).SequenceEqual(small));
if (res != null) {
    Console.Println("Found at {0}", res.Value);
} else {
    Console.Println("Not found");
}

除了 Cast<int?> 之外，该方法不言自明。部分:您需要它来决定在 large 的初始位置查找结果。数组，当返回零时，根本找不到结果，当返回为 null 时.

这是一个demo on ideone .

上面的复杂度是O(M*N) , 其中M和 N是 large 的长度和 small阵列。如果large数组很长，并且包含大量“几乎正确”的子序列，这些子序列与 small 的长前缀匹配，您最好实现一种高级算法来搜索序列，例如 Knuth–Morris–Pratt (KMP) algorithm . KMP 算法通过观察当不匹配发生时加速搜索，small序列包含关于您可以在 large 中前进多远的足够信息基于小序列中第一个不匹配位置的序列。为 small 准备了一个查找表序列，然后在整个搜索过程中使用该表来决定如何推进搜索点。 KMP 的复杂度为 O(N+M) .有关 KMP 算法的伪代码，请参阅上面链接的维基百科文章。