C#中带Null通配符的Boyer-Moore算法实现异常问题咨询

问题描述 #

尝试在C#中实现支持Null通配符（模式串中的null可匹配任意字节）的Boyer-Moore算法，代码在模式串不含null时运行正常，但包含null（如0xAA, 0xBB, null, 0xCC）时会丢失部分匹配结果。原实现代码如下：

class BoyerMoore
{
    private readonly int[] _badChar;
    private readonly byte?[] _needle;

    public BoyerMoore(byte?[] needle)
    {
        _needle = needle;
        _badChar = new int[256];

        // Pre-processing for bad character heuristic
        for (int i = 0; i < _badChar.Length; i++)
        {
            _badChar[i] = -1;
        }
        for (int i = 0; i < needle.Length; i++)
        {
            if (needle[i] != null)
                _badChar[needle[i].Value] = i;
        }
    }

    public List<int> Search(byte[] haystack)
    {
        List<int> occurrences = new List<int>();
        int i = 0;
        while (i <= haystack.Length - _needle.Length)
        {
            int j;

            for (j = _needle.Length - 1; j >= 0; j--)
            {
                if (_needle[j] == null) continue;
                if (_needle[j] != haystack[i + j]) break;
            }

            if (j < 0)
            {
                occurrences.Add(i);
                i++;
            }
            else
            {
                i += Math.Max(1, j - _badChar[haystack[i + j]]);
            }
        }
        return occurrences;
    }
}

问题原因 #

标准Boyer-Moore的坏字符启发式跳转逻辑基于模式串全为固定字符的假设：当匹配失败时，根据当前不匹配字符在模式中的最后出现位置计算跳转步数，若字符不在模式中则直接跳转j+1步。但引入Null通配符后，该逻辑会跳过潜在的匹配位置——因为通配符可匹配任意字符，即使当前不匹配的字符不在模式固定字符中，仍可能存在某个偏移位置让该字符被通配符匹配，过大的跳转步数会直接跳过这些位置。

比如模式为[0xBB, null, 0xAA]、 haystack为[0xAA, 0xBB, 0xCC, 0xAA]时，原代码会从i=0直接跳转3步到i=3，错过i=1的有效匹配。

修复方案 #

新增预处理逻辑记录模式串每个位置左侧最近的通配符位置，在计算跳转步数时，取坏字符启发式步数和基于通配符的最小安全步数中的较小值，确保不会跳过可能的匹配位置。

修复后的代码：

class BoyerMoore
{
    private readonly int[] _badChar;
    private readonly byte?[] _needle;
    private readonly int[] _leftWildcard; // 记录每个位置左侧最近的通配符位置

    public BoyerMoore(byte?[] needle)
    {
        _needle = needle;
        _badChar = new int[256];
        _leftWildcard = new int[needle.Length];

        // 预处理坏字符启发式数组
        for (int i = 0; i < _badChar.Length; i++)
        {
            _badChar[i] = -1;
        }
        for (int i = 0; i < needle.Length; i++)
        {
            if (needle[i] != null)
                _badChar[needle[i].Value] = i;
        }

        // 预处理左侧最近通配符位置数组
        int lastWildcardPos = -1;
        for (int i = 0; i < needle.Length; i++)
        {
            if (needle[i] == null)
            {
                lastWildcardPos = i;
            }
            _leftWildcard[i] = lastWildcardPos;
        }
    }

    public List<int> Search(byte[] haystack)
    {
        List<int> occurrences = new List<int>();
        int i = 0;
        int needleLength = _needle.Length;

        while (i <= haystack.Length - needleLength)
        {
            int j;

            // 从后往前匹配，跳过通配符
            for (j = needleLength - 1; j >= 0; j--)
            {
                if (_needle[j] == null) continue;
                if (_needle[j] != haystack[i + j]) break;
            }

            if (j < 0)
            {
                // 匹配成功，记录位置
                occurrences.Add(i);
                // 可优化为启发式跳转，此处用i++保证不丢失重叠匹配
                i++;
            }
            else
            {
                byte currentChar = haystack[i + j];
                // 计算坏字符跳转步数
                int badCharStep = j - _badChar[currentChar];
                // 计算基于通配符的安全跳转步数：若左侧无通配符则按标准逻辑跳j+1，否则跳至最近通配符的下一个位置
                int wildcardStep = _leftWildcard[j] == -1 ? (j + 1) : (j - _leftWildcard[j]);
                // 取最大的安全跳转步数（避免跳步过小影响效率，同时保证不跳过有效位置）
                i += Math.Max(1, Math.Min(badCharStep, wildcardStep));
            }
        }
        return occurrences;
    }
}

说明 #

1. 预处理左侧通配符位置：遍历模式串，记录每个位置左侧最近的通配符索引，若左侧无通配符则记为-1。
2. 跳转逻辑调整：匹配失败时，同时计算坏字符启发式步数和通配符安全步数，取两者中的较小值作为实际跳转步数，既保证效率，又避免跳过潜在匹配位置。
3. 匹配成功后的跳转：此处保留i++以支持重叠匹配，若不需要重叠匹配，可改为启发式跳转（如基于好后缀规则）进一步提升效率。

内容的提问来源于stack exchange，提问作者작은녹음방