3

假设我有一个大的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 方法可以做到这一点，我也会采用（尽管为了教育起见，我仍然很欣赏搜索算法的名称）。

4

2 回答 2

4

您可以使用 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。

这是关于 ideone 的演示。

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

于 2013-04-11T03:09:00.913 回答
0

你在想 Lambda 表达式吗？当你说一种更具体的字符串方法时，这就是我想到的。

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

于 2013-04-11T03:05:15.683 回答