Comment trouver l'index de la sous-liste dans la liste?

Question

Je cherche un moyen efficace (en .NET), comment trouver s'il y a une séquence d'octets dans une liste d'octets et s'il y en a, index où le premier commence.

Par exemple disons que j'ai:

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

et le résultat devrait être que ma séquence est l'indice 3 dans le LISTONE et l'indice -1 (.-À-dire qu'il est pas là) dans le listTwo.

Bien sûr, je peux parcourir la liste int par int et depuis chaque index et rechercher si les nombres suivants correspondent à ma séquence, mais y a-t-il un moyen plus efficace (par exemple en utilisant des méthodes d'extension)?

Answer 1

Je suggérerais de convertir chaque List<int> en String puis de chercher en utilisant le String.IndexOf(sequence) pour déterminer où ou si la séquence est présente.

Answer 2

Ceci est essentiellement le même problème que la recherche de sous-chaîne (en effet, une liste où l'ordre est significatif est une généralisation de "chaîne").

Heureusement, l'informatique a souvent considéré ce problème depuis longtemps, vous permettant ainsi de rester sur les épaules des géants.

Regardez la littérature. Quelques points de départ sont raisonnables:

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

Même que le pseudo-code dans les articles wikipedia est suffisant pour port C# assez facilement. Regardez les descriptions de performance dans différents cas et décidez quels cas sont les plus susceptibles d'être rencontrés par votre code. (Je pense le premier de ce que vous dites à propos de la liste de clés de recherche étant court).

Answer 3

Je pense que la façon la plus propre est de créer une méthode d'extension générique comme ceci:

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

pour appeler ainsi:

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

post-scriptum vous pouvez également commencer à partir d'un index donné, si vous devez rechercher d'autres occurrences de sous-listes