эквивалент strstr() в C#

Question

У меня два byte[] и я хочу найти первое вхождение второго byte[] во-первых byte[] (или диапазон в нем).

Я не хочу использовать строки для эффективности (перевод первого byte[] к string будет неэффективно).

В принципе я верю, что это то, что strstr() делает в C.

Как лучше всего это сделать (чтобы он был эффективным и простым в использовании)?

Вот как это должно выглядеть:

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

Спасибо!

ОБНОВЛЯТЬ:

Мне нужно решение, которое было бы более эффективным, чем простой поиск.Это означает, что, учитывая тот факт, что сравнение буферов может быть более эффективным, следует использовать - memcmp() более эффективен, чем перебор байтов.

Кроме того, я знаю, что существуют алгоритмы, оптимизирующие подобные сценарии:

• большой массив:"12312351231234"
• небольшой массив:"1231234"
• Наивный алгоритм: 7 сравнивает и обнаруживает, что «1231235» отличается от «1231234», 2 сравнивает, чтобы найти следующую «1», 4 сравнивает, чтобы обнаружить, что «1235» отличается от «1231», 3 сравнивает, чтобы найти следующую «1», 7 сравнивает, чтобы найти совпадение.Всего 7+2+4+3+7=23 сравнения.
• Умный алгоритм: 7 сравнивает и обнаруживает, что «1231235» отличается от «1231234», непосредственно переходит к следующей «1» (без сравнения), 4 сравнивает и обнаруживает, что «1235» отличается от «1231», напрямую переходит за «5». , 7 сравнивает, чтобы найти совпадение.Всего 7+4+7=18 сравнений.

Answer 1

У меня нет никакого кода для вас, но имя самого быстрого решения, которое вы найдете, является Бойер-Мур алгоритм. Это может сделать лучше, чем o (n).

Здесь это реализация для строк на кодовомпроекте. Выглядит как преобразование в byte[] не должно быть слишком сложно.

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

ОБНОВЛЕНО;(надеюсь) Исправлена ​​проблема, о которой меня предупредил Хенк.

ОБНОВЛЕНИЕ 2:Адресация обновления исходного вопроса:

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

В теории алгоритма хорошо известно, что оптимизация для скорости стоит память и наоборот. Мой алгоритм использует немного больше памяти (не так много), но взамен сканирует большой массив один раз.

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

Список starts используется для отслеживания потенциальных начинающих смещений smallArray в bigArray. Отказ Это никогда не будет содержать больше элементов, чем количество вхождений smallArray[0] в smallArray (которые могут быть рассчитаны заранее, чтобы оптимизировать список и уменьшить количество Reallocation Memory). Когда не хватает байтов, оставленных в bigArray содержать smallArray, это не пробовал, а когда smallArray Был найден, алгоритм останавливается. Это также останавливается, когда конец bigArray Был достигнут. Там, что время работы в худшем случае будет o (1), а использование памяти будет o (1).

Дополнительные возможные оптимизации включают использование указателей в небезопасном коде и замена списка фиксированным массивом, размер которого можно рассчитать заранее (как отмечено ранее). Однако, поскольку в списке неверные смещения удалены (меньший внутренний цикл) и в массиве неправильные смещения должны быть пропущены (фиксированный размер внутренней петли, но, возможно, более быстрый доступ к элементу), вам придется ориентироваться, который быстрее.

Это также имеет значение, если вы ожидаете smallArray быть большим или нет. Когда вы делаете, вы можете добавить чек на цикл While, которая проверяет ли starts.Length != 0 || offset <= (bigArrayOffset + bigArrayCount - smallArray.Length). Отказ В противном случае цикл может остановиться, и никаких вхождений не было найдено.

Answer 4

Вот мой взять на решение. Это разделено в два. Первая часть в основном ищет потенциальный запуск. Если он найдет один из него, сравнивает список с обоих концов (для снижения количества петли, который в основном является микро оптимизацией без профилирования, но как правило Это быстрее)

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