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

Question

我试图在一个字节数组中连续查找一个字节数组 (byte[])，我发现了一个只能找到第一次出现的代码。

这是我找到代码的地方： Find an array (byte[]) inside another array?

问题：下面这段代码如何连续查找字节数组？

        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添加到索引中，以便我们在先前找到的结果结束后立即开始搜索。

更新：

以下是如何使用此代码创建一个方法，该方法 returns 将索引作为数组：

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 algorithm，如果 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);

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

c# How to Continuously find a byte array inside a byte array?

c#

arrays

search

byte

find