c＃如何在字节数组内连续查找字节数组？

Question

我试图不断地在一个字节数组中找到一个字节数组（byte []），并且我找到了一个只能找到第一个出现的代码。

这是我找到的代码：Find an array (byte[]) inside another array?

问题：我怎样才能不断找到下面这段代码的字节数组？

 public int SearchBytes(byte[] haystack, byte[] needle) 
    { 
     int len = needle.Length; 
     int limit = haystack.Length - len; 
     for (int i = 0; i <= limit; i++) 
     { 
      int k = 0; 
      for (; k < len; k++) 
      { 
       if (needle[k] != haystack[i + k]) break; 
      } 
      if (k == len) return i; 
     } 
     return -1; 
    } 

Answer 1

您可以更改方法接受起始索引是这样的：

public int SearchBytes(byte[] haystack, byte[] needle, int start_index) 
{ 
    int len = needle.Length; 
    int limit = haystack.Length - len; 
    for (int i = start_index; i <= limit; i++) 
    { 
     int k = 0; 
     for (; k < len; k++) 
     { 
      if (needle[k] != haystack[i + k]) break; 
     } 
     if (k == len) return i; 
    } 
    return -1; 
} 

的差别只是在于这个方法接受一个start_index，并开始在这个特定的索引搜索。现在

，你可以使用它像这样：

byte[] haystack = new byte[] { 1, 2, 3, 4, 5, 1, 2, 3 }; 

byte[] needle = new byte[] {1,2,3}; 

int index = 0; 

while (true) 
{ 
    index = SearchBytes(haystack, needle, index); 

    if (index == -1) 
     break; 

    Console.WriteLine("Found at " + index); 

    index += needle.Length; 
} 

这个循环对指数0开始，那么它使用以前的搜索设置新的指数开始下一次搜索的结果。

它将needle.Length添加到索引，以便我们在先前找到的结果结束后立即开始搜索。

UPDATE：

下面是该代码是如何可以被用来创建一个返回的索引作为阵列的方法：

public int[] SearchBytesMultiple(byte[] haystack, byte[] needle) 
{ 
    int index = 0; 

    List<int> results = new List<int>(); 

    while (true) 
    { 
     index = SearchBytes(haystack, needle, index); 

     if (index == -1) 
      break; 

     results.Add(index); 

     index += needle.Length; 
    } 

    return results.ToArray(); 
} 

它可以像这样使用：

byte[] haystack = new byte[] { 1, 2, 3, 4, 5, 1, 2, 3 }; 

byte[] needle = new byte[] {1,2,3}; 

int[] indexes = SearchBytesMultiple(haystack, needle); 

Answer 2

作为一种替代方案，您可以考虑使用Boyer-Moore algorithm，如果尺寸为，这是非常高效的或haystack[]很大。

但是，我不会推荐这个很短的needle[]或haystack[]，因为建立偏移表的开销将比仅进行简单的线性搜索更高。

下面是我从Java一个转换的Wiki页面，我链接上实现：

using System; 
using System.Collections.Generic; 

namespace ConsoleApplication1 
{ 
    public sealed class BoyerMoore 
    { 
     readonly byte[] needle; 
     readonly int[] charTable; 
     readonly int[] offsetTable; 

     public BoyerMoore(byte[] needle) 
     { 
      this.needle  = needle; 
      this.charTable = makeByteTable(needle); 
      this.offsetTable = makeOffsetTable(needle); 
     } 

     public IEnumerable<int> Search(byte[] haystack) 
     { 
      if (needle.Length == 0) 
       yield break; 

      for (int i = needle.Length - 1; i < haystack.Length;) 
      { 
       int j; 

       for (j = needle.Length - 1; needle[j] == haystack[i]; --i, --j) 
       { 
        if (j != 0) 
         continue; 

        yield return i; 
        i += needle.Length - 1; 
        break; 
       } 

       i += Math.Max(offsetTable[needle.Length - 1 - j], charTable[haystack[i]]); 
      } 
     } 

     static int[] makeByteTable(byte[] needle) 
     { 
      const int ALPHABET_SIZE = 256; 
      int[] table = new int[ALPHABET_SIZE]; 

      for (int i = 0; i < table.Length; ++i) 
       table[i] = needle.Length; 

      for (int i = 0; i < needle.Length - 1; ++i) 
       table[needle[i]] = needle.Length - 1 - i; 

      return table; 
     } 

     static int[] makeOffsetTable(byte[] needle) 
     { 
      int[] table = new int[needle.Length]; 
      int lastPrefixPosition = needle.Length; 

      for (int i = needle.Length - 1; i >= 0; --i) 
      { 
       if (isPrefix(needle, i + 1)) 
        lastPrefixPosition = i + 1; 

       table[needle.Length - 1 - i] = lastPrefixPosition - i + needle.Length - 1; 
      } 

      for (int i = 0; i < needle.Length - 1; ++i) 
      { 
       int slen = suffixLength(needle, i); 
       table[slen] = needle.Length - 1 - i + slen; 
      } 

      return table; 
     } 

     static bool isPrefix(byte[] needle, int p) 
     { 
      for (int i = p, j = 0; i < needle.Length; ++i, ++j) 
       if (needle[i] != needle[j]) 
        return false; 

      return true; 
     } 

     static int suffixLength(byte[] needle, int p) 
     { 
      int len = 0; 

      for (int i = p, j = needle.Length - 1; i >= 0 && needle[i] == needle[j]; --i, --j) 
       ++len; 

      return len; 
     } 
    } 
} 

下面是一些测试代码：

byte[] haystack = new byte[1000]; 
byte[] needle = {1, 2, 3, 4, 5, 6, 7, 8, 9}; 

for (int i = 100; i <= 900; i += 100) 
    Array.Copy(needle, 0, haystack, i, needle.Length); 

var searcher = new BoyerMoore(needle); 

foreach (int index in searcher.Search(haystack)) 
    Console.WriteLine(index);