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 比较查找下一个“1”，7 比较查找匹配。总共7+2+4+3+7=23次比较。
• 智能算法：7次比较发现“1231235”与“1231234”不同，直接跳转到下一个“1”（不比较），4次比较发现“1235”与“1231234”不同1231”，直接跳过“5”，7比较找到匹配的。总共7+4+7=18次比较。

Answer 1

我没有任何代码给您，但您会找到的最快解决方案的名称是 Boyer-Moore 算法。它可以比 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 用于跟踪 bigArray 中 smallArray 的潜在起始偏移量。它所包含的元素永远不会多于 smallArray[0] 在 smallArray 中出现的次数（可以提前计算以优化列表并减少内存重新分配的次数） ）。当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;
    }
}