编辑距离是量化两字符串差异的最小单字符操作数（插入、删除、替换），数值越小越相似；它是模糊匹配的数学基础，通过设阈值实现容错匹配，而非精确匹配。
什么是编辑距离，它和模糊匹配有什么关系
编辑距离（Levenshtein Distance）是两个字符串之间，由一个转换成另一个所需的最少单字符编辑操作数（插入、删除、替换）。它不等于“相似度百分比”，但能直接量化差异程度——数值越小，越接近。实际做模糊匹配时，你不是靠它返回“true/false”，而是算出距离后自己设阈值，比如 distance 就认为匹配成功。
用动态规划实现标准编辑距离函数
手动写比调第三方库更可控，尤其嵌入式或无 STL 环境。核心是二维 DP 表：dp[i][j] 表示 s1 前 i 个字符变到 s2 前 j 个字符的最小编辑距离。
常见错误：数组索引越界、初始化遗漏第一行/列、没处理空字符串边界。
- 初始化：
dp[i][0] = i（删掉 s1 前 i 字符），dp[0][j] = j（插入 j 字符） - 状态转移：
dp[i][j] = dp[i-1][j-1]如果s1[i-1] == s2[j-1]；否则取min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 - 空间可优化：只用两行滚动数组，避免 O(m×n) 内存 —— 对长字符串很关键
如何避免重复计算，提升模糊匹配性能
如果你要拿一个查询串对几千个候选串做模糊匹配，每次都跑完整 DP 是低效的。几个实用策略：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
- 提前剪枝：若当前已累计编辑操作数 > 阈值，立即返回（可用递归+限界，或 DP 过程中加判断）
- 长度过滤：若
abs(len(s1) - len(s2)) > threshold，直接跳过 —— 编辑距离不可能小于长度差 - 预处理候选集：对固定词典，可构建 BK-tree 或使用 Levenshtein automaton，但 C++ 标准库不自带，需额外引入或手写
- 注意：
std::string的.data()和.c_str()在空串时行为一致，但传给自定义函数前建议先检查 length() 是否为 0
为什么 std::string::find 不适合模糊匹配
std::string::find 只做精确子串查找，哪怕只差一个字符就完全失败。有人误用它配合循环尝试所有子串，再拼接距离计算——这既没降低复杂度，又容易漏掉跨位置的编辑（比如 “abc” → “acb” 是换位，非子串关系）。真正模糊匹配必须基于字符对齐的编辑模型，而不是滑动窗口匹配。
编辑距离本身不区分大小写，也不处理音似或语义，这些得靠额外规则（比如先统一转小写，或叠加 Soundex）。最常被忽略的是：阈值选择严重依赖业务场景——查人名用 2，查命令行指令可能只能容忍 1，而日志关键词匹配有时放宽到 3 仍可接受。没有通用最优值。
