strstr () équivalent en C #

Question

J'ai deux byte[] et je veux trouver la première occurrence du deuxième byte[] dans la première byte[] (ou une plage en elle).

Je ne veux pas utiliser des chaînes pour l'efficacité (traduisant la première byte[] à un string sera inefficace).

En fait, je crois que ce que strstr() qu'en C.

Quelle est la meilleure façon de le faire (il est efficace et facile à utiliser)?

Voici comment cela devrait ressembler à:

int GetOffsetOfArrayInArray(byte[] bigArray, int bigArrayOffset, int bigArrayCount, byte[] smallArray);

Merci!

Mise à jour:

Je veux une solution qui serait plus efficace qu'une recherche simple. Cela signifie que en utilisant le fait que la comparaison des tampons peuvent être plus efficaces devrait être utilisé - memcmp () est plus efficace que itérer sur les octets .

De plus, je sais qu'il ya des algorithmes qui permettent d'optimiser les scénarios comme celui-ci:

• grand tableau: "12312351231234"
• petit tableau: "1231234"
• algorithme Naive: 7 compare à constater que « 1231235 » est différent de « 1.231.234 », 2 compare pour trouver le prochain « 1 », 4 compare à constater que « 1235 » est différent de " 1231" , 3 compare pour trouver le prochain « 1 », 7 compare pour trouver correspondance. Un total de 7 + 2 + 4 + 3 + 7 = 23 compare.
• algorithme Smart: 7 compare à constater que « 1231235 » est différent de « 1.231.234 », saute directement à l'autre « 1 » (sans comparer), 4 compare à constater que « 1235 » est différent de « 1231 », saute directement au-delà du « 5 », 7 compare pour trouver le match. Un total de 7 + 4 + 7 = 18 compare.

Answer 1

Je ne vous trouverez pas de code pour vous, mais le nom de la solution la plus rapide est le l'algorithme de Boyer-Moore. Il peut faire mieux que O (n).

est une implémentation pour les chaînes sur CodeProject. On dirait une conversion à byte[] ne devrait pas être trop difficile.

Answer 2

int GetOffsetOfArrayInArray(byte[] bigArray, int bigArrayOffset, 
                               int bigArrayCount, byte[] smallArray)
{
     byte first = smallArray[0];
     bool cont= true;
     while (cont && 
            bigArrayOffset=Array.IndexOf(bigArray, first, bigArrayOffset) != -1)
     {
         if (bigArrayOffset + smallArray.Length > bigArray.Length)
         {
              bigArrayOffset = -1;
              break;
         }
         cont= false;
         for(int i=1; i< smallArray.Length; ++i)
         {
              if (bigArray[bigArrayOffset+i] != smallArray[i])
              { 
                 ++bigArrayOffset;
                 cont = true;
                 break;
              }
         }
     }
     return bigArrayOffset;
}

mise à jour; (Je l'espère) Correction d'un problème Henk me alerté.

MISE À JOUR 2: Aborder mise à jour à la question initiale:

int GetOffsetOfArrayInArray(byte[] bigArray, int bigArrayOffset, 
                               int bigArrayCount, byte[] smallArray)
{
     int bigArrayEnd = Math.Min(bigArrayCount + bigArrayOffset, bigArray.Length)
     byte first = smallArray[0];
     bool cont= true;
     while (cont && 
            bigArrayOffset=Array.IndexOf(bigArray, first, bigArrayOffset) != -1)
     {
         int bookmark = bigArrauOffset + 1;
         bool bookmarkset = false;
         if (bigArrayOffset + smallArray.Length > bigArrayEnd )
         {
              bigArrayOffset = -1;
              break;
         }
         cont= false;
         for(int i=1; i< smallArray.Length; ++i)
         {
              if (!bookmarkset && bigArray[bigArrayOffset+i] == first)
              {
                   bookmark = bigArrayOffset+i;
                   bookmarkset = true;
              }
              if (bigArray[bigArrayOffset+i] != smallArray[i])
              { 
                 bigArrayOffset = bookmark;
                 cont = true;
                 break;
              }
         }
     }
     return bigArrayOffset;
}

Answer 3

Dans l'algorithme théorie, il est bien connu que l'optimisation pour les coûts de la vitesse mémoire et vice versa. Mon algorithme utilise un peu plus de mémoire (pas beaucoup), mais en retour scanne seulement le grand tableau une fois.

public static int GetOffsetOfArrayInArray(byte[] bigArray, int bigArrayOffset, int bigArrayCount, byte[] smallArray)
{
    // TODO: Check whether none of the variables are null or out of range.
    if (smallArray.Length == 0)
        return 0;

    List<int> starts = new List<int>();    // Limited number of elements.

    int offset = bigArrayOffset;
    // A single pass through the big array.
    while (offset < bigArrayOffset + bigArrayCount)
    {
        for (int i = 0; i < starts.Count; i++)
        {
            if (bigArray[offset] != smallArray[offset - starts[i]])
            {
                // Remove starts[i] from the list.
                starts.RemoveAt(i);
                i--;
            }
            else if (offset - starts[i] == smallArray.Length - 1)
            {
                // Found a match.
                return starts[i];
            }
        }
        if (bigArray[offset] == smallArray[0] &&
            offset <= (bigArrayOffset + bigArrayCount - smallArray.Length))
        {
            if (smallArray.Length > 1)
                // Add the start to the list.
                starts.Add(offset);
            else
                // Found a match.
                return offset;
        }
        offset++;
    }
    return -1;
}

La liste starts est utilisé pour suivre les décalages de départ potentiels de smallArray dans bigArray. Il ne contient plus d'éléments que le nombre d'occurrences de smallArray[0] dans smallArray (qui peut être calculée à l'avance afin d'optimiser la liste et de réduire le nombre de réaffectations de mémoire). Quand il n'y a pas assez d'octets laissés dans bigArray pour contenir smallArray, il est pas essayé, et quand smallArray a été trouvé, l'algorithme s'arrête. Il arrête aussi quand a atteint la fin de bigArray. À cet effet, le pire des cas temps d'exécution serait O (1), et l'utilisation de la mémoire serait O (1).

D'autres optimisations possibles comprennent l'utilisation de pointeurs dans un code dangereux, et le remplacement de la liste par un réseau fixe, dont la taille peut être calculée à l'avance (comme indiqué précédemment). Cependant, parce que dans la mauvaise liste décalages sont supprimés (petite boucle interne) et dans un tableau mauvais décalages doivent être sautée (taille fixe boucle intérieure, mais l'accès de l'élément peut-être plus rapide), vous auriez à référence que l'on est plus rapide.

Il importe également que vous attendez smallArray d'être grand ou non. Lorsque vous le faites, vous pouvez ajouter un chèque à la boucle while qui vérifie si starts.Length != 0 || offset <= (bigArrayOffset + bigArrayCount - smallArray.Length). Sinon, la boucle peut arrêter et aucun cas n'a été trouvé.

Answer 4

Voici mon avis sur une solution. Il est divisé en deux. La première partie recherche principalement pour un démarrage potentiel. Si elle trouve un, il la compare la liste des deux extrémités (pour abaisser le nombre de boucles qui est essentiellement une micro optimisation avec un profileur mais habituellement il est plus rapide)

int GetOffsetOfArrayInArray(byte[] bigArray,
                        int bigArrayOffset,
                        int bigArrayCount,
                        byte[] smallArray)
    {
        var length = smallArray.Length;
        var lastPossibleStart = bigArray.Length - length;
        var startByte = smallArray[0];

        for (var first = bigArrayOffset; first < lastPossibleStart; first++)
        {
           if (bigArray[first] == startByte &&
               check(bigArray, smallArray, first, length))
           {
              return first;
           }
        }
        return -1;
    }

    bool check(byte[] bigArray, byte[] smallArray, int first, int length)
    {
        var smallIndex = 0;
        var smallLast = length - 1;
        var last = first + length - 1;
        for (var i = first; smallIndex <= smallLast; i++)
        {
            if (bigArray[i] != smallArray[smallIndex] ||
                 bigArray[last] != smallArray[smallLast])
            {
                return false;
            }
            smallIndex = i - first + 1;
            last--;
            smallLast--;
        }
        return true;
    }
}