¿Cómo determinar que una matriz es una parte de otra?

Question

Por ejemplo: Tengo gama

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

que saben método rápido para encontrar el índice de la matriz de la etiqueta? necesito algo de la siguiente manera:

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

una secuencia puede estar en más de un momento en src.

Solución: 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

Aquí es una manera de obtener el índice 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); 
} 

Por desgracia, es muy lento.

Si lo que desea es saber si todos los artículos en tag se pueden encontrar en src (en cualquier orden), entonces

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

Lo mejor que se puede conseguir es O (m), pero que poco compleja implementación. Si satisface con una solución que tiene O (m * n) como el peor caso, puede ir con la solución a continuación. Si sus secuencias están ordenadas y el ítem inicial en la matriz tag solo está presente una vez en src, esto también dará como resultado 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; 
    } 
} 

asumí la secuencia tiene que ser en ese orden y sólo han compilado en Firefox, así que no sé si funciona :). Además, lo hice genérico para que maneje cualquier tipo de matrices, no solo bytes.

ACTUALIZACIÓN: El código actualizado se compila y funciona ... o mi simple prueba funcionó.

Answer 4

Esta tarea es igual a la subcadena de búsqueda en la cadena. Para esto puede usar cualquier algoritmo KMP para un mejor rendimiento: http://exclusiveminds.com/2009/12/09/kmp-string-searching-algorithm-in-c/

Answer 5

Solución encontrada.

How to find index of sublist in list?