搜索列表中的一個數組或列表

Question

有

List<byte> lbyte 

有

byte[] searchBytes 

如何搜索1字節的不只是一個字節但對於searchBytes的指數？
E.G.

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

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

Answer 2

蠻力總是一種選擇。雖然與其他方法相比較慢，但實際上通常不會太差。如果lbyte不是很大，並且沒有病理數據，那麼實施起來很容易並且完全可以接受。

它與brute force string searching的概念相同。

Answer 3

的另一種方式，你可以用lambda表達式

int index = lbyte.FindIndex(e => searchBytes.All(i => i.Equals(e));