Jak ustalić, że jedna tablica jest częścią innej?

Question

Na przykład: Mam tablica

var src = new byte[] {1, 2, 3, 4, 5}; 
var tag = new byte[] {3, 4}; 

którzy znają szybki sposób na znalezienie indeks tablicy zawieszki? muszę coś jak następuje:

int FindIndexOfSeq(byte[] src, byte[] sequence); 

sekwencja może mieć więcej niż jeden razy w src.

Rozwiązanie: How to find index of sublist in list?

Answer 1

int FindIndexOfSeq<T>(byte[] src, byte[] tag) 
{ 
    Int32 tagCount = tag.Count();    

    // If `tag` is not empty and `src` contains `tag` 
    if (tagCount > 0 && src.Intersect(tag).Count() == tagCount) 
    { 
     // Find index of first element in `tag` 
     Int32 tagStartIndex = Array.IndexOf(src, tag.First()); 

     // Get the matching slice of `tag` from `src` 
     var newSrc = src.Skip(tagStartIndex).Take(tag.Count()).ToList(); 

     // Zip them together using their difference 
     var sum = Enumerable.Zip(tag, newSrc, (i1, i2) => Convert.ToInt32(i2 - i1)).Sum(); 

     // If total of their differences is zero, both sequences match 
     if (sum == 0) 
     { 
      // return starting index of `tag` in `src` 
      return tagStartIndex; 
     } 
    } 

    // return `Not Found` 
    return -1; 
} 

Answer 2

Oto jedna droga do uzyskania indeksu

for (int i = 0; i < (src.Length - tag.Length); i++) 
{ 
    if (tag.SequenceEqual(src.Skip(i).Take(tag.Length))) 
     Console.WriteLine("It's at position " + i); 
} 

Niestety jest to bardzo powolny.

Jeśli chcesz tylko wiedzieć, czy wszystkie elementy w tag można znaleźć w src (w dowolnej kolejności), a następnie

var src = new byte[] { 1, 2, 3, 4, 5 }; 
var tag = new byte[] { 4, 3 }; 

if (src.Intersect(tag).Count() == tag.Length) 
    Console.WriteLine("tag can be found in src!"); 

Answer 3

najlepiej można uzyskać wynosi O (m), ale że ja nieco skomplikowane realizacja. Jeśli spełniasz rozwiązanie, które ma O (m * n) jako najgorszy przypadek, możesz skorzystać z poniższego rozwiązania. Jeśli twoje sekwencje są uporządkowane, a element początkowy w tablicy tag jest obecny tylko raz w src, spowoduje to również O (m).

class Program 
{ 
    static void Main(string[] args) 
    { 
     var src = new byte[] { 1, 2, 3, 4, 5 }; 
     var tag = new byte[] { 3, 4 }; 
     var index = FindIndexOfSeq(src, tag); 
     Console.WriteLine(index); 
     Console.ReadLine(); 
    } 
    static int FindIndexOfSeq<T>(T[] src, T[] seq) 
    { 
     int index = -1; 
     for (int i = 0; i < src.Length - seq.Length + 1; i++) 
     { 
      bool foundSeq = true; 
      for (int j = 0; j < seq.Length; j++) 
      { 
       foundSeq = foundSeq && src[i + j].Equals(seq[j]); 
      } 
      if (foundSeq) 
      { 
       index = i; 
       break; 
      } 
     } 
     return index; 
    } 
} 

Założę, że sekwencja musi być w tej kolejności, a ja skompilowałem ją tylko w firefoxie, więc nie wiem, czy to działa :). Zrobiłem też rodzajowy, więc obsługuje każdy rodzaj tablic nie tylko bajtów.

AKTUALIZACJA: Zaktualizowany kod kompiluje się i działa ... lub mój prosty test zadziałał.

Answer 4

Zadanie to jest równe szukaniu podciągów w łańcuchu. W tym celu można użyć dowolnego algorytmu KMP dla lepszej wydajności: http://exclusiveminds.com/2009/12/09/kmp-string-searching-algorithm-in-c/

Answer 5

Rozwiązanie znalezione.

How to find index of sublist in list?