SQL LIKE实现通配符匹配过急问题的非回溯修复方案咨询

我找到一个模拟SQL LIKE函数的C#扩展方法，整体表现良好，但存在%通配符匹配过急的问题，导致特定测试用例失败。例如测试"hawkeye".Like("ha%k%e")时，逻辑上应该匹配ha[w]k[ey]e返回true，但实际因为第一个%会过度匹配到字符串末尾，导致后续的%e无法找到匹配，返回false。

原函数代码 #

public static bool Like(this string s, string match, bool CaseInsensitive = true)
{
    //Nothing matches a null mask or null input string
    if (match == null || s == null)
        return false;
    //Null strings are treated as empty and get checked against the mask.
    //If checking is case-insensitive we convert to uppercase to facilitate this.
    if (CaseInsensitive)
    {
        s = s.ToUpperInvariant();
        match = match.ToUpperInvariant();
    }
    //Keeps track of our position in the primary string - s.
    int j = 0;
    //Used to keep track of multi-character wildcards.
    bool matchanymulti = false;
    //Used to keep track of multiple possibility character masks.
    string multicharmask = null;
    bool inversemulticharmask = false;
    for (int i = 0; i < match.Length; i++)
    {
        //If this is the last character of the mask and its a % or * we are done
        if (i == match.Length - 1 && (match[i] == '%' || match[i] == '*'))
            return true;
        //A direct character match allows us to proceed.
        var charcheck = true;
        //Backslash acts as an escape character.  If we encounter it, proceed
        //to the next character.
        if (match[i] == '\\')
        {
            i++;
            if (i == match.Length)
                i--;
        }
        else
        {
            //If this is a wildcard mask we flag it and proceed with the next character
            //in the mask.
            if (match[i] == '%' || match[i] == '*')
            {
                matchanymulti = true;
                continue;
            }
            //If this is a single character wildcard advance one character.
            if (match[i] == '_')
            {
                //If there is no character to advance we did not find a match.
                if (j == s.Length)
                    return false;
                j++;
                continue;
            }
            if (match[i] == '[')
            {
                var endbracketidx = match.IndexOf(']', i);
                //Get the characters to check for.
                multicharmask = match.Substring(i + 1, endbracketidx - i - 1);
                //Check for inversed masks
                inversemulticharmask = multicharmask.StartsWith("^");
                //Remove the inversed mask character
                if (inversemulticharmask)
                    multicharmask = multicharmask.Remove(0, 1);
                //Unescape \^ to ^
                multicharmask = multicharmask.Replace("\\^", "^");
                
                //Prevent direct character checking of the next mask character
                //and advance to the next mask character.
                charcheck = false;
                i = endbracketidx;
                //Detect and expand character ranges
                if (multicharmask.Length == 3 && multicharmask[1] == '-')
                {
                    var newmask = "";
                    var first = multicharmask[0];
                    var last = multicharmask[2];
                    if (last < first)
                    {
                        first = last;
                        last = multicharmask[0];
                    }
                    var c = first;
                    while (c <= last)
                    {
                        newmask += c;
                        c++;
                    }
                    multicharmask = newmask;
                }
                //If the mask is invalid we cannot find a mask for it.
                if (endbracketidx == -1)
                    return false;
            }
        }
        //Keep track of match finding for this character of the mask.
        var matched = false;
        while (j < s.Length)
        {
            //This character matches, move on.
            if (charcheck && s[j] == match[i])
            {
                j++;
                matched = true;
                break;
            }
            //If we need to check for multiple charaters to do.
            if (multicharmask != null)
            {
                var ismatch = multicharmask.Contains(s[j]);
                //If this was an inverted mask and we match fail the check for this string.
                //If this was not an inverted mask check and we did not match fail for this string.
                if (inversemulticharmask && ismatch ||
                    !inversemulticharmask && !ismatch)
                {
                    //If we have a wildcard preceding us we ignore this failure
                    //and continue checking.
                    if (matchanymulti)
                    {
                        j++;
                        continue;
                    }
                    return false;
                }
                j++;
                matched = true;
                //Consumse our mask.
                multicharmask = null;
                break;
            }
            //We are in an multiple any-character mask, proceed to the next character.
            if (matchanymulti)
            {
                j++;
                continue;
            }
            break;
        }
        //We've found a match - proceed.
        if (matched)
        {
            matchanymulti = false;
            continue;
        }

        //If no match our mask fails
        return false;
    }
    //Some characters are left - our mask check fails.
    if (j < s.Length)
        return false;
    //We've processed everything - this is a match.
    return true;
}

测试用例 #

Console.WriteLine("hawkeye".Like("ha%k%e")); // 预期true，实际返回false

问题核心 #

当前逻辑中，遇到%通配符后会设置matchanymulti = true，后续匹配字符时会一直向后移动字符串指针j，直到找到匹配项。但如果后续匹配失败，直接返回false，没有尝试让之前的%少匹配几个字符再重试——也就是缺少有限回溯的逻辑。

修复方案（无需重写为状态机） #

通过添加回溯点记录，当匹配失败且处于matchanymulti状态时，回退指针重新尝试匹配。具体修改如下：

public static bool Like(this string s, string match, bool CaseInsensitive = true)
{
    if (match == null || s == null)
        return false;
    if (CaseInsensitive)
    {
        s = s.ToUpperInvariant();
        match = match.ToUpperInvariant();
    }
    int j = 0;
    bool matchanymulti = false;
    string multicharmask = null;
    bool inversemulticharmask = false;
    // 新增回溯记录变量：记录上一个%对应的mask位置和字符串位置
    int lastWildcardPos = -1;
    int lastStringPos = -1;

    for (int i = 0; i < match.Length; i++)
    {
        if (i == match.Length - 1 && (match[i] == '%' || match[i] == '*'))
            return true;
        var charcheck = true;

        if (match[i] == '\\')
        {
            i++;
            if (i == match.Length)
                i--;
        }
        else
        {
            if (match[i] == '%' || match[i] == '*')
            {
                matchanymulti = true;
                // 记录当前位置，用于后续回溯
                lastWildcardPos = i;
                lastStringPos = j;
                continue;
            }
            if (match[i] == '_')
            {
                if (j == s.Length)
                    return false;
                j++;
                continue;
            }
            if (match[i] == '[')
            {
                var endbracketidx = match.IndexOf(']', i);
                if (endbracketidx == -1)
                    return false;
                multicharmask = match.Substring(i + 1, endbracketidx - i - 1);
                inversemulticharmask = multicharmask.StartsWith("^");
                if (inversemulticharmask)
                    multicharmask = multicharmask.Remove(0, 1);
                multicharmask = multicharmask.Replace("\\^", "^");
                
                charcheck = false;
                i = endbracketidx;
                if (multicharmask.Length == 3 && multicharmask[1] == '-')
                {
                    var newmask = "";
                    var first = multicharmask[0];
                    var last = multicharmask[2];
                    if (last < first)
                    {
                        first = last;
                        last = multicharmask[0];
                    }
                    var c = first;
                    while (c <= last)
                    {
                        newmask += c;
                        c++;
                    }
                    multicharmask = newmask;
                }
            }
        }

        var matched = false;
        while (j < s.Length)
        {
            if (charcheck && s[j] == match[i])
            {
                j++;
                matched = true;
                break;
            }
            if (multicharmask != null)
            {
                var ismatch = multicharmask.Contains(s[j]);
                if ((inversemulticharmask && ismatch) || (!inversemulticharmask && !ismatch))
                {
                    if (matchanymulti)
                    {
                        j++;
                        continue;
                    }
                    // 匹配失败，尝试回溯
                    if (lastWildcardPos != -1)
                    {
                        // 回退到上一个%的位置，让它多匹配一个字符
                        i = lastWildcardPos;
                        j = lastStringPos + 1;
                        lastStringPos = j;
                        matchanymulti = true;
                        multicharmask = null;
                        matched = true;
                        break;
                    }
                    return false;
                }
                j++;
                matched = true;
                multicharmask = null;
                break;
            }
            if (matchanymulti)
            {
                j++;
                continue;
            }
            break;
        }

        if (matched)
        {
            matchanymulti = false;
            continue;
        }

        // 全局匹配失败，尝试回溯
        if (lastWildcardPos != -1)
        {
            i = lastWildcardPos;
            j = lastStringPos + 1;
            lastStringPos = j;
            matchanymulti = true;
            // 防止无限循环：如果字符串指针无法再前进，直接返回false
            if (j >= s.Length)
                return false;
            continue;
        }

        return false;
    }

    // 如果最后还有%通配符，允许剩余字符存在
    if (matchanymulti)
        return true;
    return j >= s.Length;
}

修改说明 #

1. 新增回溯记录变量：lastWildcardPos记录上一个%通配符在mask中的位置，lastStringPos记录对应的字符串指针位置，用于后续回退重试。
2. 遇到%时记录位置：每次处理%通配符时，更新回溯点。
3. 匹配失败时触发回溯：当某个字符匹配失败且存在有效的回溯点时，回退mask指针到上一个%的位置，字符串指针向后移动一位，让之前的%多匹配一个字符，然后重新尝试匹配后续mask。
4. 防止无限循环：当字符串指针已经到末尾时，停止回溯直接返回false。

测试修改后的代码，"hawkeye".Like("ha%k%e")会正确返回true，同时保留原方法的其他功能。

内容的提问来源于stack exchange，提问作者Mason Wheeler