c＃等效的strstr（）

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，3比较找到下一个“ 1”，1”，1”，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）做得更好。

这里 是在CodeProject上的字符串实现。看起来像是转换为 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 （可以预先计算以优化列表并减少内存重新分配的数量）。当没有足够的字节中 bigArray 包含装有 smallArray, ，没有尝试，什么时候 smallArray 已经发现，算法停止。它也停止了 bigArray 已达到。因此，最坏的情况运行时间是O（1），并且内存使用率为O（1）。

进一步的优化包括在不安全的代码中使用指针，并用固定数组替换列表，该数组可以预先计算大小（如前所述）。但是，由于在列表中删除了错误的偏移（较小的内部循环），并且在数组中必须跳过错误的偏移（固定尺寸的内部循环，但可能更快的元素访问），因此您必须基准测试一个更快的速度。

您是否期望 smallArray 大小。当您这样做时，您可以将支票添加到Wiel循环中，以检查是否检查是否 starts.Length != 0 || offset <= (bigArrayOffset + bigArrayCount - smallArray.Length). 。否则，循环可能会停止并且未发现任何事件。

Answer 4

这是我对解决方案的看法。它分为两分。第一部分主要寻找潜在的开始。如果找到一个，则将两端的列表进行比较（降低循环计数，这基本上是带有Profiler的微型优化，但是 通常 更快）

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