有
List<byte> lbyte
有
byte[] searchBytes
如何搜索lbyte不仅仅是一个字节,而是搜索searchBytes的索引？
例如.
Int32 index = lbyte.FirstIndexOf(searchBytes);
这是我提出的蛮力.
不是我要找的表现.
public static Int32 ListIndexOfArray(List<byte> lb,byte[] sbs)
{
if (sbs == null) return -1;
if (sbs.Length == 0) return -1;
if (sbs.Length > 8) return -1;
if (sbs.Length == 1) return lb.FirstOrDefault(x => x == sbs[0]);
Int32 sbsLen = sbs.Length;
Int32 sbsCurMatch = 0;
for (int i = 0; i < lb.Count; i++)
{
if (lb[i] == sbs[sbsCurMatch])
{
sbsCurMatch++;
if (sbsCurMatch == sbsLen)
{
//int index = lb.FindIndex(e => sbs.All(f => f.Equals(e))); // fails to find a match
IndexOfArray = i - sbsLen + 1;
return;
}
}
else
{
sbsCurMatch = 0;
}
}
return -1;
}
解决方法
你可能会发现
Boyer-Moore algorithm在这里很有用.将列表转换为数组并进行搜索.算法代码取自
this post.
static int SimpleBoyerMooreSearch(byte[] haystack,byte[] needle)
{
int[] lookup = new int[256];
for (int i = 0; i < lookup.Length; i++) { lookup[i] = needle.Length; }
for (int i = 0; i < needle.Length; i++)
{
lookup[needle[i]] = needle.Length - i - 1;
}
int index = needle.Length - 1;
var lastByte = needle.Last();
while (index < haystack.Length)
{
var checkByte = haystack[index];
if (haystack[index] == lastByte)
{
bool found = true;
for (int j = needle.Length - 2; j >= 0; j--)
{
if (haystack[index - needle.Length + j + 1] != needle[j])
{
found = false;
break;
}
}
if (found)
return index - needle.Length + 1;
else
index++;
}
else
{
index += lookup[checkByte];
}
}
return -1;
}
然后你可以这样搜索.如果lbyte在一段时间后保持不变,你可以将它转换为一个数组并传递它.
//index is returned,or -1 if 'searchBytes' is not found int startIndex = SimpleBoyerMooreSearch(lbyte.ToArray(),searchBytes);
根据评论更新.这是IList实现,这意味着可以传递数组和列表(以及实现IList的任何其他内容)
static int SimpleBoyerMooreSearch(IList<byte> haystack,IList<byte> needle)
{
int[] lookup = new int[256];
for (int i = 0; i < lookup.Length; i++) { lookup[i] = needle.Count; }
for (int i = 0; i < needle.Count; i++)
{
lookup[needle[i]] = needle.Count - i - 1;
}
int index = needle.Count - 1;
var lastByte = needle[index];
while (index < haystack.Count)
{
var checkByte = haystack[index];
if (haystack[index] == lastByte)
{
bool found = true;
for (int j = needle.Count - 2; j >= 0; j--)
{
if (haystack[index - needle.Count + j + 1] != needle[j])
{
found = false;
break;
}
}
if (found)
return index - needle.Count + 1;
else
index++;
}
else
{
index += lookup[checkByte];
}
}
return -1;
}
由于数组和列表实现了IList,因此在您的情况下调用它时不需要进行转换.
int startIndex = SimpleBoyerMooreSearch(lbyte,searchBytes);
