在较大的byte[]中查找byte[]，类似于String's IndexOf()

本文关键字：byte String IndexOf 查找 类似于 | 更新日期: 2023-09-27 18:08:38

假设我有一个较大的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

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

我依稀记得在string中读到过一种特定的方法，但是我不记得算法的名字了。我可以很容易地写一些方法来做这件事，但我知道有一个很好的解决方案，它就在我的舌尖上。如果有一些。net方法可以做到这一点，我也会采用它(尽管出于教育的考虑，我仍然希望搜索算法的名称)。

在较大的byte[]中查找byte[]，类似于String's IndexOf()

你可以用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?>部分之外，该方法是不言自明的:您需要它决定在返回0时在large数组的初始位置查找结果，以及在返回为null时根本不查找结果。

这是一个ideone的演示。

以上复杂度为O(M*N)，其中M和N分别为large和small数组的长度。如果large数组非常长，并且包含大量与small的长前缀匹配的"几乎正确"的子序列，则最好实现用于搜索序列的高级算法，例如 KMP算法。KMP算法通过观察当不匹配发生时，small序列包含足够的信息来加快搜索速度，这些信息可以根据小序列中第一个不匹配的位置在large序列中向前移动多远。为small序列准备一个查找表，然后在整个搜索过程中使用该表来决定如何推进搜索点。KMP的复杂度为O(N+M)。参见上面链接的维基百科文章，获取KMP算法的伪代码。

你在考虑Lambda表达式吗?这就是当你说到一个更具体的字符串处理方法时，我想到的。

http://www.dotnetperls.com/array-find

相关文章：