Znajdź tablicę (byte []) wewnątrz innej tablicy?

Question

Jaki jest najprostszy sposób na znalezienie bajtu [] w innym bajcie []? Mam wrażenie, że mogę to zrobić z linq, ale nie wiem jak.

Uwaga: Zrobiłem wyszukiwanie z [c#] i nie znalazłem niczego, jestem zaskoczony.

Answer 1

Oto prosty (naiwny?) Sposób to zrobić:

static int search(byte[] haystack, byte[] needle) 
{ 
    for (int i = 0; i <= haystack.Length - needle.Length; i++) 
    { 
     if (match(haystack, needle, i)) 
     { 
      return i; 
     } 
    } 
    return -1; 
} 

static bool match(byte[] haystack, byte[] needle, int start) 
{ 
    if (needle.Length + start > haystack.Length) 
    { 
     return false; 
    } 
    else 
    { 
     for (int i = 0; i < needle.Length; i++) 
     { 
      if (needle[i] != haystack[i + start]) 
      { 
       return false; 
      } 
     } 
     return true; 
    } 
} 

Answer 2

prawdopodobnie mógłbyś sam to wymyślić, ale czasami lubię robić prostą rzecz.

bool found = false; 
int i = 0; 
for(; i < byteArray.Length || found; i++) 
{ 
    if(byteArray[i] == lookingFor) 
    { 
    found = true; 
    } 
} 

Answer 3

Spróbuj jednego z wykorzystaniem wyrażeń lambda:

private bool CheckPatternInArray(byte[] array, byte[] pattern) 
{ 
    int fidx = 0; 
    int result = Array.FindIndex(array, 0, array.Length, (byte b) => 
      { 
       fidx = (b == pattern[fidx]) ? fidx + 1 : 0; 
       return (fidx == pattern.Length); 
      }); 
    return (result >= pattern.Length - 1); 
} 

jeśli jesteś po najszybszym jeden, sprawdź rozwiązania here.

Answer 4

Oto szybsza wersja Ergwun's excellent answer:

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

W krótkim teście z stogu siana 11MB i igły 9 bajtów, to było około trzy razy szybciej.

optymalizacje są:

• bez funkcji połączenia każdorazowo przez zewnętrzną pętlę.
• Długość igły i limit wyszukiwania są buforowane.
• Test nadmiarowej długości na początku match() został usunięty.

Oczywiście dla tablic z długim bajtem warto użyć czegoś takiego jak wyszukiwanie Boyera-Moore'a, ale dla wielu celów prosty algorytm, taki jak ten, jest wystarczająco dobry i ma zaletę, że jest krótki i łatwy w użyciu. zrozumieć i zweryfikować.