c# 如何在字节数组中连续查找字节数组

Question

我正在尝试在字节数组中连续查找一个字节数组（byte[]），但我发现了一个只能找到第一次出现的代码。

这是我找到代码的地方：在另一个数组中查找一个数组（byte[]）？

问：如何使用下面的代码连续找到字节数组？

        public int SearchBytes(byte[] haystack, byte[] needle)
    {
        int len = needle.Length;
        int limit = haystack.Length - len;
        for (int i = 0; i <= limit; i++)
        {
            int k = 0;
            for (; k < len; k++)
            {
                if (needle[k] != haystack[i + k]) break;
            }
            if (k == len) return i;
        }
        return -1;
    }

Answer 1

您可以更改方法以接受启动索引，如下所示：

public int SearchBytes(byte[] haystack, byte[] needle, int start_index)
{
    int len = needle.Length;
    int limit = haystack.Length - len;
    for (int i = start_index; i <= limit; i++)
    {
        int k = 0;
        for (; k < len; k++)
        {
            if (needle[k] != haystack[i + k]) break;
        }
        if (k == len) return i;
    }
    return -1;
}

区别只是此方法接受start_index并在此特定索引处开始搜索。

现在，您可以像这样使用它：

byte[] haystack = new byte[] { 1, 2, 3, 4, 5, 1, 2, 3 };
byte[] needle = new byte[] {1,2,3};
int index = 0;
while (true)
{
    index = SearchBytes(haystack, needle, index);
    if (index == -1)
        break;
    Console.WriteLine("Found at " + index);
    index += needle.Length;
}

此循环从索引 0 开始，然后使用上一个搜索的结果来设置新索引以开始下一个搜索。

它将needle.Length添加到索引中，以便我们在先前找到的结果结束后立即开始搜索。

更新：

下面介绍如何使用此代码创建将索引作为数组返回的方法：

public int[] SearchBytesMultiple(byte[] haystack, byte[] needle)
{
    int index = 0;
    List<int> results = new List<int>();
    while (true)
    {
        index = SearchBytes(haystack, needle, index);
        if (index == -1)
            break;
        results.Add(index);
        index += needle.Length;
    }
    return results.ToArray();
}

它可以像这样使用：

byte[] haystack = new byte[] { 1, 2, 3, 4, 5, 1, 2, 3 };
byte[] needle = new byte[] {1,2,3};
int[] indexes = SearchBytesMultiple(haystack, needle);

Answer 2

作为替代方案，您可以考虑使用 Boyer-Moore 算法，如果 needle[] 或 haystack[] 的大小很大，该算法的性能非常高。

但是，对于非常短的needle[]或haystack[]，我不建议这样做，因为设置偏移表的开销将高于仅执行简单的线性搜索。

这是我在我链接的 Wiki 页面上从 Java 转换的一个实现：

using System;
using System.Collections.Generic;
namespace ConsoleApplication1
{
    public sealed class BoyerMoore
    {
        readonly byte[] needle;
        readonly int[]  charTable;
        readonly int[]  offsetTable;
        public BoyerMoore(byte[] needle)
        {
            this.needle      = needle;
            this.charTable   = makeByteTable(needle);
            this.offsetTable = makeOffsetTable(needle);
        }
        public IEnumerable<int> Search(byte[] haystack)
        {
            if (needle.Length == 0)
                yield break;
            for (int i = needle.Length - 1; i < haystack.Length;)
            {
                int j;
                for (j = needle.Length - 1; needle[j] == haystack[i]; --i, --j)
                {
                    if (j != 0)
                        continue;
                    yield return i;
                    i += needle.Length - 1;
                    break;
                }
                i += Math.Max(offsetTable[needle.Length - 1 - j], charTable[haystack[i]]);
            }
        }
        static int[] makeByteTable(byte[] needle)
        {
            const int ALPHABET_SIZE = 256;
            int[] table = new int[ALPHABET_SIZE];
            for (int i = 0; i < table.Length; ++i)
                table[i] = needle.Length;
            for (int i = 0; i < needle.Length - 1; ++i)
                table[needle[i]] = needle.Length - 1 - i;
            return table;
        }
        static int[] makeOffsetTable(byte[] needle)
        {
            int[] table = new int[needle.Length];
            int lastPrefixPosition = needle.Length;
            for (int i = needle.Length - 1; i >= 0; --i)
            {
                if (isPrefix(needle, i + 1))
                    lastPrefixPosition = i + 1;
                table[needle.Length - 1 - i] = lastPrefixPosition - i + needle.Length - 1;
            }
            for (int i = 0; i < needle.Length - 1; ++i)
            {
                int slen = suffixLength(needle, i);
                table[slen] = needle.Length - 1 - i + slen;
            }
            return table;
        }
        static bool isPrefix(byte[] needle, int p)
        {
            for (int i = p, j = 0; i < needle.Length; ++i, ++j)
                if (needle[i] != needle[j])
                    return false;
            return true;
        }
        static int suffixLength(byte[] needle, int p)
        {
            int len = 0;
            for (int i = p, j = needle.Length - 1; i >= 0 && needle[i] == needle[j]; --i, --j)
                ++len;
            return len;
        }
    }
}

下面是一些测试代码：

byte[] haystack = new byte[1000];
byte[] needle   = {1, 2, 3, 4, 5, 6, 7, 8, 9};
for (int i = 100; i <= 900; i += 100)
    Array.Copy(needle, 0, haystack, i, needle.Length);
var searcher = new BoyerMoore(needle);
foreach (int index in searcher.Search(haystack))
    Console.WriteLine(index);