检查一个字节[]是否包含在另一个字节[]中的最佳方法 [英] Best way to check if a byte[] is contained in another byte[]

问题描述

可能重复:
byte []阵列模式搜索

你好

搜索一个字节[]是否在另一个字节[]中的最佳方法是什么.

Whats the best way to search if a byte[] is in another byte[].

例如

byte[] first = new byte[] { 0x01, 0x02, 0x03, 0x04, 0x05 };
byte[] second = new byte[] { 0x01, 0x02 };
byte[] third = new byte[] { 0x01, 0x03 };

该方法将返回:

first.Contains(second); // true
first.Contains(third); // false
second.Contains(third); // false

谢谢！

推荐答案

您可以使用Jb的<​​a href ="https://stackoverflow.com/questions/283456/byte-array-pattern-search/283648#283648">定位方法，并在第一个比赛中尽早出现

you could use Jb's Locate method and early out on the first match

例如:

static class ByteArrayRocks
{

    public static bool Contains(this byte[] self, byte[] candidate)
    {
        if (IsEmptyLocate(self, candidate))
            return false;

        for (int i = 0; i < self.Length; i++)
        {
            if (IsMatch(self, i, candidate))
                return true;
        }

        return false;
    }

    static bool IsMatch(byte[] array, int position, byte[] candidate)
    {
        if (candidate.Length > (array.Length - position))
            return false;

        for (int i = 0; i < candidate.Length; i++)
            if (array[position + i] != candidate[i])
                return false;

        return true;
    }

    static bool IsEmptyLocate(byte[] array, byte[] candidate)
    {
        return array == null
                || candidate == null
                || array.Length == 0
                || candidate.Length == 0
                || candidate.Length > array.Length;
    }
}

class Program
{
    static void Main()
    {
        var data = new byte[] { 23, 36, 43, 76, 125, 56, 34, 234, 12, 3, 5, 76, 8, 0, 6, 125, 234, 56, 211, 122, 22, 4, 7, 89, 76, 64, 12, 3, 5, 76, 8, 0, 6, 125 };
        var pattern = new byte[] { 12, 3, 5, 76, 8, 0, 6, 125,11 };

        Console.WriteLine(data.Contains(pattern));


        Console.ReadKey();
    }
}

这将比 Boyer-Moore 的效率低得多.某些数组，因为如果不匹配，它可以更快地跳过数组.除其他算法外，还有C#实现.此处.

This would be much less efficient than Boyer-Moore for certain arrays, as it is able to skip through the array much faster if there is a mismatch. There are C# implementation of this amongst many others algorithms here.

这是使用它和horspool的Wikipedia实现的改编.

This is an adaptation using it and the wikipedia implementation of horspool.

static class Horspool
{
    private static int[] BuildBadSkipArray(byte[] needle)
    {
        const int MAX_SIZE = 256;

        int[] skip = new int[MAX_SIZE];
        var needleLength = needle.Length;

        for (int c = 0; c < MAX_SIZE; c += 1)
        {
            skip[c] = needleLength;
        }

        var last = needleLength - 1;

        for (int scan = 0; scan < last; scan++)
        {
            skip[needle[scan]] = last - scan;
        }

        return skip;
    }

    public static bool ContainsHorspool(this byte[] haystack, byte[] needle)
    {
        var hlen = haystack.Length;
        var nlen = needle.Length;
        var badCharSkip = BuildBadSkipArray(needle);
        var last = nlen - 1;

        int offset = 0;
        int scan = nlen;

        while (offset + last < hlen)
        {

            for (scan = last; haystack[scan + offset] == needle[scan]; scan = scan - 1)
            {
                if (scan == 0)
                {
                    return true;
                }
            }

            offset += badCharSkip[haystack[scan + offset]];

        }

        return false;
    }
}

这篇关于检查一个字节[]是否包含在另一个字节[]中的最佳方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！