¿Cómo encontrar el índice de sublista en la lista?

Question

Estoy buscando una forma eficiente (en .NET), cómo encontrar si hay una secuencia de bytes en alguna lista de bytes y si hay alguna, índice donde comienza la primera.

Por ejemplo digamos que tengo:

var sequence = new List<byte> { 5, 10, 2 }; 
var listOne = new List<byte> { 1, 3, 10, 5, 10, 2, 8, 9 }; 
var listTwo = new List<byte> { 1, 3, 10, 5, 2, 10, 8, 9 }; 

y el resultado debe ser que mi secuencia es el índice de las 3 de la LISTONE y en el índice de -1 (. Es decir, que no está ahí) en el listTwo.

Por supuesto, puedo recorrer la lista int por int y de cada índice y buscar si los siguientes números coinciden con mi secuencia, pero ¿hay alguna forma más eficiente (por ejemplo, utilizando métodos de extensión)?

Answer 1

Sugeriría convertir cada List<int> en String y luego buscar usando String.IndexOf(sequence) para determinar dónde o si la secuencia está presente.

Answer 2

Esto es esencialmente el mismo problema que la búsqueda de subcadenas (de hecho, una lista donde el orden es significativo es una generalización de "cadena").

Afortunadamente, la informática ha considerado este problema con frecuencia durante mucho tiempo, por lo que se pone de pie sobre los hombros de los gigantes.

Eche un vistazo a la literatura. Algunos puntos de partida razonables son:

http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

http://en.wikipedia.org/wiki/Rabin-karp

Aunque sólo el pseudocódigo en los artículos de Wikipedia es suficiente para el puerto de C# con bastante facilidad. Mire las descripciones del rendimiento en diferentes casos y decida qué casos es más probable que encuentre su código. (Estoy pensando que lo primero que dices sobre la lista de claves de búsqueda es corto).

Answer 3

Creo que la forma más limpia es crear un método de extensión genérica como esto:

public static int SubListIndex<T>(this IList<T> list, int start, IList<T> sublist) 
{ 
    for (int listIndex = start; listIndex < list.Count - sublist.Count + 1; listIndex++) 
    { 
     int count = 0; 
     while (count < sublist.Count && sublist[count].Equals(list[listIndex + count])) 
      count++; 
     if (count == sublist.Count) 
      return listIndex; 
    } 
    return -1; 
} 

que llaman de esta manera:

var indexOne = listOne.SubListIndex(0, sequence); 
var indexTwo = listTwo.SubListIndex(0, sequence); 

P. S. también puede comenzar desde un índice dado, si necesita buscar más ocurrencias de sublistas