C++实现支持通配符的字符串匹配算法 _ 递归与动态规划思路实现【源码】-C++-PHP中文网

std::regex 不适合轻量通配符匹配，因其默认支持完整正则语义、启动开销大、过度解析 * 和 ?，而手写逻辑更可控、更快、noexcept 且无依赖。

c++实现支持通配符的字符串匹配算法 _ 递归与动态规划思路实现【源码】

为什么 `std::regex` 不适合轻量通配符匹配

因为 std::regex 默认支持完整正则语义（如捕获组、回溯控制、Unicode），启动开销大，且对 * 和 ? 这类简单通配符会过度解析。实际项目中若只需 POSIX shell 风格匹配（? 匹配单字符，* 匹配任意长度子串），手写逻辑更可控、更快、无依赖。

常见错误是直接把 std::regex 当作通配符引擎用，结果在嵌入式或高频调用场景下触发大量内存分配和状态机跳转，CPU cache 友好性差。

通配符模式不含 ^、$、[a-z] 等扩展语法时，不必引入正则库
std::regex 构造函数本身可能抛 std::regex_error，而手写逻辑可全程 noexcept
递归实现若未加记忆化，最坏情况会退化成指数级（如 "****" 匹配长字符串）

递归解法：如何避免重复计算和栈溢出

核心思路是按字符逐位推进：遇到普通字符直接比；遇到 ? 跳过一位；遇到 * 则尝试“匹配 0 个”或“匹配至少 1 个”，形成分支。

关键陷阱是不加缓存的朴素递归——比如模式 "a*b*c" 匹配 "aaabbbccc" 时，* 的多次分叉会导致同一子问题（如 s[3..] vs p[2..]）被反复计算。

必须用二维 memo[i][j] 记录 s.substr(i) 是否能被 p.substr(j) 匹配，类型为 std::optional<bool></bool> 或三态数组（-1=未算，0=false，1=true）
递归出口要覆盖三种边界：j == p.size()（模式耗尽，要求文本也耗尽）、i == s.size()（文本耗尽，模式剩余只能全是 *）
不要用 std::string::substr() 传参，改用索引 + 引用，避免构造临时子串

示例关键判断：

if (memo[i][j].has_value()) return memo[i][j].value();
if (j == p.size()) return i == s.size();
if (i == s.size()) return std::all_of(p.begin() + j, p.end(), [](char c) { return c == '*'; });