strstr () equivalente en C #

Question

Tengo dos byte[] y yo quiero encontrar la primera aparición de la segunda byte[] en el primer byte[] (o un rango en ella).

No quiero utilizar cadenas para la eficiencia (la traducción de la primera byte[] a un string será ineficiente).

Básicamente creo que eso es lo que ocurre en C strstr().

¿Cuál es la mejor manera de hacerlo (por lo que sea eficiente y fácil de usar)?

Esta es la forma en que debe ser similar:

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

Gracias!

ACTUALIZACIÓN:

Quiero una solución que sería más eficiente que una simple búsqueda. Esto significa que utilizando el hecho de que los tampones que comparan pueden ser más eficientes se debe utilizar - memcmp () es más eficiente que iterar sobre los bytes .

Además, sé que existen algoritmos que los escenarios Optimizar como ésta:

• gran variedad: "12312351231234"
• pequeño array: "1231234"
• algoritmo Naive: 7 compara para encontrar que "1231235" es diferente de "1231234", 2 compara para encontrar la siguiente "1", 4 compara para encontrar que "1235" es diferente de " 1231" , 3 compara a encontrar el siguiente '1', 7 compara para encontrar pareja. Un total de 7 + 2 + 4 + 3 + 7 = 23 compara.
• Smart algoritmo: 7 compara para encontrar que "1231235" es diferente de "1231234", directamente salta a la siguiente "1" (sin comparar), 4 compara para encontrar que "1235" se diferente de "1231", salta directamente más allá del "5", 7 compara para encontrar la combinación. Un total de 7 + 4 + 7 = 18 compara.

Answer 1

No tengo ningún código para usted, pero el nombre de la solución más rápida que encontrará es la algoritmo de Boyer-Moore . Se puede hacer mejor que O (n).

Aquí es una implementación para cuerdas en CodeProject. Se parece a una conversión a byte[] no debe ser demasiado difícil.

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

actualizadas; problema (con suerte) fijo Henk me alertó.

ACTUALIZACIÓN 2: Abordar la actualización a la pregunta original:

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

En el algoritmo teoría, es bien sabido que la optimización de velocidad cuesta memoria y viceversa. Mi algoritmo utiliza un poco más de memoria (no mucho) pero a cambio sólo explora la gran variedad de una vez.

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

El starts lista se utiliza para realizar un seguimiento de los posibles desplazamientos de inicio de smallArray en bigArray. Nunca será contener más elementos que el número de ocurrencias de smallArray[0] en smallArray (que puede ser calculado de antemano para optimizar la lista y reducir el número de reasignaciones de memoria). Cuando no hay suficientes bytes que quedan en bigArray para contener smallArray, no se intentó, y cuando se ha encontrado smallArray, el algoritmo se detiene. También se detiene cuando se ha alcanzado el final de bigArray. Para ello, el peor de los casos el tiempo de funcionamiento sería O (1), y el uso de memoria sería O (1).

optimizaciones adicionales posibles incluyen el uso de punteros en código no seguro, y la sustitución de la lista con una matriz fija cuyo tamaño se puede calcular de antemano (como se ha señalado antes). Sin embargo, debido a que en la lista de desplazamientos incorrectos se eliminan (bucle interno más pequeño) y en una matriz desplazamientos incorrectos tienen que ser omitidos (bucle interno de tamaño fijo, pero el acceso elemento posiblemente más rápido), usted tendría que índice de referencia que uno es más rápido.

También importa si espera que smallArray a ser grande o no. Cuando lo hace, se podría agregar un cheque para el bucle while que comprueba si starts.Length != 0 || offset <= (bigArrayOffset + bigArrayCount - smallArray.Length). De lo contrario el bucle puede parar y no se han encontrado ocurrencias.

Answer 4

Esta es mi opinión sobre una solución. Está dividida en dos. La primera parte busca sobre todo para un inicio potencial. Si encuentra uno que la compara la lista de ambos extremos (para bajar la cuenta de bucle que es básicamente una optimización de micro con un perfilador pero general es más rápido)

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