Comment rechercher un tableau avec un tableau?

Question

J'ai 2 tableaux d'octets:

Dim A() As Byte = {1, 2, 3, 4, 5, 6, 7, 8, 9} 
    Dim B() As Byte = {5, 6, 7} 

Maintenant Je veux trouver l'occurance de la pleine B en A. J'ai essayé Array.IndexOf (A, B) sans chance. Y at-il un moyen simple de rechercher un tableau par tableau sans avoir besoin d'utiliser des boucles?

Il devrait trouver l'index (position) de 5,6,7 dans le même ordre que dans B(). Si A() contient {1,2,3,4, 7,6,5, 9} il doit retourner false ou -1 car ils ne sont pas dans le même ordre.

Answer 1

La déclaration LINQ suivante donnera une IEnumerable<int> contenant les positions de b dans un (ou un vide définir si aucun ne se produit):

Enumerable 
    .Range(0, 1 + a.Length - b.Length) 
    .Where(i => a.Skip(i).Take(b.Length).SequenceEqual(b)); 

Je n'ai aucune idée de la façon de traduire vers VB.NET.

Answer 2

Que diriez-vous de créer une méthode:

1. Concatinates les éléments de la liste recherchée à une chaîne
2. Concatinates les éléments de la liste pour rechercher une chaîne
3. Attend dans la première chaîne pour la precense de la deuxième chaîne

comme ceci:

public bool IsSubSetOf(IList<int> list1, IList<int> list2){ 
    var string1 = string.Join("", list1); 
    var string2 = string.Join("", list2); 
    return string1.Contains(string2); 
} 

Non testé ...

Answer 3

Un moyen efficace de résoudre ce problème en général est le KMP algorithm. Le googling rapide suggère qu'une implémentation .NET peut être trouvée here. Son pseudocode d'implémentation est disponible depuis Wikipedia.

Un inefficace, mais sans dommage facile à moyen de code est présenté dans l'un des liens ci-dessus comme suit:

int[] T = new[]{1, 2, 3, 4, 5}; 
int[] P = new[]{3, 4}; 

for (int i = 0; i != T.Length; i++) 
{ 
    int j = 0 
    for (;i+j != T.Length && j != P.Length && T[i+j]==P[j]; j++); 
    if (j == P.Length) return i; 
} 

Answer 4

Cela pourrait fonctionner, mais il est C# et utilise une boucle:

private static int[] GetIndicesOf(byte[] needle, byte[] haystack) 
{ 
    int[] foundIndices = new int[needle.Length]; 

    int found = 0; 

    for (int i = 0; i < haystack.Length; i++) 
    { 

     if (needle[found] == haystack[i]) 
     { 
      foundIndices[found++] = i; 

      if (found == needle.Length) 
       return foundIndices; 
     } 
     else 
     { 
      i -= found; // Re-evaluate from the start of the found sentence + 1 
      found = 0; // Gap found, reset, maybe later in the haystack another occurrance of needle[0] is found 
      continue; 
     } 
    } 

    return null;    
} 

testé avec entrée:

Byte[] haystack = { 5, 6, 7, 8, 9, 0, 5, 6, 7 }; 
Byte[] needle = { 5, 6, 7 }; 
// Returns {0, 1, 2} 

Byte[] haystack = { 5, 6, 0, 8, 9, 0, 5, 6, 7 }; 
Byte[] needle = { 5, 6, 7 }; 
// Returns {6, 7, 8} 

Byte[] haystack = { 5, 6, 0, 7, 9, 0, 5, 6, 8 }; 
Byte[] needle = { 5, 6, 7 }; 
// Returns null 

Byte[] haystack = { 1, 2, 1, 2, 2 }; 
Byte[] needle = { 1, 2, 2 }; 
// Returns {2, 3, 4} 

Byte[] haystack = { 1, 2, 1, 2, 1, 2, 3 }; 
Byte[] needle = { 1, 2, 1, 2, 3 }; 
// Returns {2, 3, 4, 5, 6} 

Byte[] haystack = { 1, 1, 1, 1, 2 }; 
Byte[] needle = { 1, 2 }; 
// Returns {3, 4} 

Mais la mise en œuvre de Linq @spender semble plus agréable. :-P

Answer 5

Mon avis serait:

public static int Search<T>(T[] space, T[] searched) { 
    foreach (var e in Array.FindAll(space, e => e.Equals(searched[0]))) { 
    var idx = Array.IndexOf(space, e); 
    if (space.ArraySkip(idx).Take(searched.Length).SequenceEqual(searched)) 
     return idx; 
    } 
    return -1; 
} 

public static class Linqy { 
    public static IEnumerable<T> ArraySkip<T>(this T[] array, int index) { 
    for (int i = index; i < array.Length; i++) { 
     yield return array[i]; 
    } 
    } 
} 

Comme toujours, cela dépend de vos données si cela est « assez bon » ou vous devrez recourir à des algorithmes encore efficaces et plus complexes. J'ai introduit un arrayskip car le skip Linq n'assume en effet que l'interface IEnumerable et énumérerait jusqu'à l'index.