Come determinare che un array sia parte di un altro?

Question

Per esempio: ho serie

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

Chi sa metodo veloce per trovare indice della serie del tag? ho bisogno di qualcosa come segue:

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

una sequenza può essere in più di una volte in src.

Soluzione: 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

Ecco un modo per ottenere l'indice del

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

Purtroppo è molto lento.

Se si vuole solo sapere se tutti gli articoli nel tag può essere trovato in src (in qualsiasi ordine) allora

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

Il meglio che si può ottenere è O (m), ma che ho un po 'complessa implementazione. Se si soddisfa con una soluzione che ha O (m * n) nel peggiore dei casi si può andare con la soluzione qui sotto. Se le sequenze sono ordinate e l'elemento iniziale nell'array tag è presente solo una volta in src, ciò comporterà anche 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; 
    } 
} 

ho assunto la sequenza devono essere in questo ordine e ho compilato solo in Firefox, quindi non so se funziona :). Inoltre, l'ho reso generico in modo che gestisca qualsiasi tipo di array, non solo i byte.

UPDATE: Il codice aggiornato compila e funziona ... oppure il mio test semplice ha funzionato.

Answer 4

Questa attività è uguale alla ricerca della sottostringa nella stringa. Per questo è possibile utilizzare qualsiasi algoritmo KMP per prestazioni migliori: http://exclusiveminds.com/2009/12/09/kmp-string-searching-algorithm-in-c/

Answer 5

Soluzione trovata.

How to find index of sublist in list?