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);