如何在带空字符间隔的大型字节数组中高效查找多个子数组？

这种带空字节间隔的字符串处理确实挺头疼的，尤其是面对百万级别的字节数组，普通的LINQ暴力匹配肯定会卡顿——毕竟每次Skip和Take都要做切片比对，时间复杂度和内存开销都太高了。

为什么你的现有方法会卡顿 #

你用的LINQ方法本质是暴力匹配，时间复杂度是O(n*m)（n是原字节数组长度，m是目标子数组长度）。对于150万长度的数组，每次比对都要截取子数组再做SequenceEqual，频繁的内存切片和循环比对会直接拖慢程序，卡顿是必然的结果。

推荐用KMP算法实现高效多匹配 #

KMP算法（Knuth-Morris-Pratt）专门解决长文本中快速查找多段子串/子数组的问题，时间复杂度能降到O(n+m)，全程在原数组上操作，没有额外的切片开销，非常适合你的百万级字节数组场景。

第一步：构建KMP前缀函数（部分匹配表） #

前缀函数的作用是记录目标子数组中，每个位置之前的子串里最长的前缀-后缀匹配长度，这样比对失败时不需要回溯原数组指针，只移动目标子数组指针，大大减少重复比对次数。

private static int[] BuildPrefixFunction(byte[] pattern)
{
    int[] prefix = new int[pattern.Length];
    int matchLength = 0; // 当前最长匹配前缀的长度

    for (int i = 1; i < pattern.Length; i++)
    {
        while (matchLength > 0 && pattern[i] != pattern[matchLength])
        {
            matchLength = prefix[matchLength - 1];
        }
        if (pattern[i] == pattern[matchLength])
        {
            matchLength++;
        }
        prefix[i] = matchLength;
    }
    return prefix;
}

第二步：实现KMP多匹配逻辑 #

基于前缀函数遍历原字节数组，找到所有匹配的起始索引并记录：

public static List<int> FindAllOccurrences(byte[] text, byte[] pattern)
{
    List<int> occurrences = new List<int>();
    if (pattern.Length == 0 || text.Length < pattern.Length)
    {
        return occurrences;
    }

    int[] prefix = BuildPrefixFunction(pattern);
    int textIndex = 0;
    int patternIndex = 0;

    while (textIndex < text.Length)
    {
        if (pattern[patternIndex] == text[textIndex])
        {
            textIndex++;
            patternIndex++;
        }

        if (patternIndex == pattern.Length)
        {
            // 找到一个匹配，记录起始索引
            occurrences.Add(textIndex - patternIndex);
            // 利用前缀函数继续查找下一个匹配
            patternIndex = prefix[patternIndex - 1];
        }
        else if (textIndex < text.Length && pattern[patternIndex] != text[textIndex])
        {
            // 不匹配时，根据前缀函数调整pattern指针
            if (patternIndex != 0)
            {
                patternIndex = prefix[patternIndex - 1];
            }
            else
            {
                textIndex++;
            }
        }
    }

    return occurrences;
}

第三步：针对你的场景适配 #

比如你要找标签"CODE"，对应的带0x00间隔的字节数组是new byte[] {0x43, 0x00, 0x4F, 0x00, 0x44, 0x00, 0x45, 0x00}，直接把这个作为pattern传入上面的方法，就能快速找到所有匹配的起始位置了。

额外性能小Tips #

• 提前构建目标标签的带间隔字节数组，避免每次查找重复生成；
• 如果要处理多个标签，可以提前缓存每个标签的前缀函数，复用计算结果；
• 避免在循环中创建新数组，全程复用原数组和预设的集合，减少内存分配开销。

内容的提问来源于stack exchange，提问作者Marcomattia Mocellin