通配符模式匹配题解

题目概述

实现一个支持通配符的模式匹配系统：

• ? 匹配任意单个字符
• * 匹配零个或多个任意字符
• 判断多个文件字符串是否匹配给定的模式

算法设计

核心思路：分段处理 + 混合匹配策略

将复杂模式按 * 分割成多个段，分别处理前缀、中间段和后缀，采用不同的匹配算法优化性能。

算法流程

1. 预处理阶段

// 按 '*' 分割模式
vector<string> segs;
string buf;
for (char c : pattern) {
    if (c == '*') {
        if (!buf.empty()) { segs.push_back(buf); buf.clear(); }
    } else buf.push_back(c);
}

2. 特殊情况处理

• 空模式：只匹配空字符串
• 全星号模式：匹配所有字符串
• 单段无星号：需要完全匹配

3. 三段式匹配

前缀匹配（无头星号）：

if (!headStar) {
    // 直接比较前 segs[0].size() 个字符
    // 使用 pat_vs_text 处理 '?' 通配符
}

后缀匹配（无尾星号）：

if (!tailStar) {
    // 从字符串末尾向前比较 segs[m-1].size() 个字符
}

中间段匹配：

• 对每个中间段预计算所有可能的匹配位置
• 使用DFS+记忆化搜索找到可行的匹配序列

4. 匹配算法选择

KMP算法（用于不含'?'的段）：

vector<int> kmp_all_exact(const string &text, const string &pat, int rightBound)

• 构建LPS数组优化匹配
• O(n+m)时间复杂度

朴素匹配（用于含'?'的段）：

vector<int> naive_all_with_q(const string &text, const string &pat, int rightBound)

• 逐个位置尝试匹配
• 处理'?'通配符

5. 搜索策略

DFS + 记忆化：

function<bool(int,int)> dfs = [&](int si, int curpos)->bool {
    if (si == rightIdx) return true;
    if (memo[si].count(curpos)) return false;
    
    // 尝试当前段的所有匹配位置
    for (每个匹配位置) {
        if (dfs(si + 1, nextPos)) return true;
    }
    
    memo[si].insert(curpos);
    return false;
};

复杂度分析

时间复杂度

• KMP匹配：O(n+m) 每段
• 朴素匹配：O(n×m) 每段
• DFS搜索：最坏O(k!)（k为中间段数），但通过记忆化剪枝

空间复杂度

• O(m + n) 存储分段和匹配位置
• O(k) 记忆化存储

算法优势

1. 适应性：根据段特征选择最优匹配算法
2. 完备性：支持通配符的所有合法组合
3. 高效性：通过预计算和记忆化避免重复工作
4. 鲁棒性：正确处理边界情况和特殊模式

关键优化点

1. 分段预计算：提前计算所有段的匹配位置
2. 记忆化剪枝：避免重复搜索失败的状态
3. 边界检查：及时排除不可能的匹配
4. 算法选择：根据段复杂度选用KMP或朴素匹配

适用场景

该算法适用于：

• 文件系统路径匹配
• 搜索引擎查询
• 正则表达式的简化版本
• 需要高效通配符匹配的各种场景

这种混合策略在保证功能完备性的同时，针对不同情况采用最优算法，实现了性能与功能的平衡。