假设我有一个大的 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 方法可以做到这一点,我也会采用它(尽管出于教育目的,我仍然很欣赏搜索算法的名称)。
最佳答案
您可以使用 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 算法的伪代码,请参阅上面链接的维基百科文章。
关于c# - 在类似于 String IndexOf() 的更大 byte[] 中寻找 byte[]?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15939958/