字符数组模式匹配问题：如何处理%的可变长度匹配？

问题概述 #

需要实现一个函数，接收字符数组形式的text和pattern，返回pattern在text中出现的匹配次数。文本仅包含数字和拉丁字母，模式支持以下特殊匹配规则：

• *：匹配恰好任意一个字符；
• %：匹配1位或2位十进制数字；
• @：匹配一个拉丁字母。

示例验证 #

1. 文本："te3t zdrte44q t33t"，模式："t*%@" → 匹配子串"te3t"、"te44q"、"t33t"，预期输出3；
2. 文本："aaaaaa"，模式："aa" → 预期输出5；
3. 文本："123"，模式："%%" → 预期输出3。

当前瓶颈 #

已实现*和@的单字符匹配逻辑，但%的可变长度（1或2位数字）匹配无法用线性步进逻辑处理，需要特殊的分支/回溯机制。

当前代码 #

#include <iostream>

using namespace std;

const int MAX_SIZE_TEXT = 201;
const int MAX_SIZE_PATTERN = 201;

unsigned getStrLen(char str[])
{
    int i = 0, count = 0;
    while (str[i] != '\0')
    {
        i++;
        count++;
    }
    return count;
}

bool isLetter(char ch)
{
    return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}

bool isDigit(char ch)
{
    return ch >= '0' && ch <= '9';
}

unsigned countMatches(char text[], char pattern[])
{
    int textLen = getStrLen(text);
    int patternLen = getStrLen(pattern);

    int i = 0, j = 0, currentLen = 0, matches = 0;

    bool matchedASingleDigit = false;
    while (i < textLen)
    {
        cout << text[i] << "?=" << pattern[j] << endl;
        if (text[i] == pattern[j] || pattern[j] == '*' 
            || (pattern[j] == '@' && isLetter(text[i])))
        {
            cout << "(before) i=" << i << "; j=" << j << endl;
            currentLen += 1;
            i++;
            j++;
            cout << "(after) i=" << i << "; j=" << j << endl;

            cout << "currentLen = " << currentLen << endl;
            if (currentLen == patternLen)
            {
                matches++;
            }
        }
        else if (pattern[j] == '%')
        {
            /*if (isDigit(text[i]))
            {
                matchedASingleDigit = true;
                currentLen += 1;
                i++;
                j++;
                cout << "(after) i=" << i << "; j=" << j << endl;

                cout << "currentLen = " << currentLen << endl;
                if (currentLen == patternLen)
                {
                    matches++;
                }
            }

            if (i < textLen - 1 && isDigit[text])*/
        }
        else
        {
            i -= currentLen - 1;
            j = 0;
            cout << "(after) i=" << i << "; j=" << j << endl;
            
            currentLen = 0;
            cout << "currentLen = " << currentLen << endl;
        }
    }

    return matches;
}

void testCountingMatches()
{
    char text[MAX_SIZE_TEXT];
    cin.getline(text, MAX_SIZE_TEXT);

    char pattern[MAX_SIZE_PATTERN];
    cin.getline(pattern, MAX_SIZE_PATTERN);

    unsigned matches = countMatches(text, pattern);

    cout << matches << endl;
}

int main()
{
    testCountingMatches();  
}

解决思路与代码实现 #

核心方案：递归回溯处理分支匹配 #

%的可变长度特性需要同时尝试两种匹配可能性（1位或2位数字），递归可以自然处理这种分支逻辑，避免手动维护复杂的状态回退。

步骤1：实现递归匹配辅助函数

该函数负责从文本的指定位置i、模式的指定位置j开始，判断后续内容是否能完全匹配：

// 辅助函数：从text[i]和pattern[j]开始匹配，返回是否能完全匹配模式
bool matchFrom(char text[], char pattern[], int i, int j, int textLen, int patternLen)
{
    // 模式匹配完成，返回成功
    if (j == patternLen)
        return true;
    // 文本已耗尽但模式未匹配完，返回失败
    if (i >= textLen)
        return false;

    // 处理普通字符、*、@的单字符匹配
    if (text[i] == pattern[j] || pattern[j] == '*' || (pattern[j] == '@' && isLetter(text[i])))
    {
        return matchFrom(text, pattern, i+1, j+1, textLen, patternLen);
    }
    // 处理%的可变长度匹配
    else if (pattern[j] == '%')
    {
        bool case1 = false;
        // 尝试匹配1位数字
        if (isDigit(text[i]))
        {
            case1 = matchFrom(text, pattern, i+1, j+1, textLen, patternLen);
        }
        
        bool case2 = false;
        // 尝试匹配2位数字（需保证文本有足够长度）
        if (i+1 < textLen && isDigit(text[i]) && isDigit(text[i+1]))
        {
            case2 = matchFrom(text, pattern, i+2, j+1, textLen, patternLen);
        }
        
        // 只要任意一种匹配方式成功，就返回真
        return case1 || case2;
    }
    // 普通字符不匹配
    else
    {
        return false;
    }
}

步骤2：修改主匹配函数

遍历文本的所有起始位置，调用辅助函数判断是否匹配，统计总次数：

unsigned countMatches(char text[], char pattern[])
{
    int textLen = getStrLen(text);
    int patternLen = getStrLen(pattern);
    unsigned matches = 0;

    // 遍历所有可能的起始位置
    for (int start = 0; start < textLen; start++)
    {
        if (matchFrom(text, pattern, start, 0, textLen, patternLen))
        {
            matches++;
        }
    }
    return matches;
}

关键注意事项 #

1. 边界检查：匹配2位数字时必须确保i+1不超出文本长度，避免数组越界；
2. 分支覆盖：%的两种匹配情况都要尝试，只要其中一种能完成整个模式匹配，就算有效；
3. 递归终止条件：必须明确模式匹配完成（j == patternLen）和文本耗尽（i >= textLen）的情况，避免无限递归。

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