编辑距离指将一个字符串转为另一个的最少单字符操作次数，常用动态规划实现，通过设定最大允许距离实现模糊搜索。
在C++中实现模糊搜索，核心思路是通过计算两个字符串之间的“距离”来衡量它们的相似度。最常用的方法是编辑距离（Levenshtein Distance）算法。它表示将一个字符串转换为另一个字符串所需的最少单字符编辑操作次数（插入、删除、替换）。
什么是编辑距离？
编辑距离可以用来判断两个字符串的相似程度。比如：
- "kitten" → "sitting" 的编辑距离是 3
- "hello" → "helli" 的编辑距离是 1
距离越小，字符串越相似。我们可以设定一个阈值，比如最大允许距离为2，超过就不算匹配，从而实现模糊搜索。
用动态规划实现编辑距离
使用二维数组 dp[i][j] 表示 str1 前 i 个字符到 str2 前 j 个字符的最小编辑距离。
立即学习“C++免费学习笔记（深入）”；
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
int levenshteinDistance(const std::string& a, const std::string& b) {
int m = a.size();
int n = b.size();
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1));
// 初始化边界：从空串变成目标串
for (int i = 0; i <= m; i++) dp[i][0] = i;
for (int j = 0; j <= n; j++) dp[0][j] = j;
// 填表
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a[i-1] == b[j-1]) {
dp[i][j] = dp[i-1][j-1]; // 相同字符，无需操作
} else {
dp[i][j] = 1 + std::min({
dp[i-1][j], // 删除
dp[i][j-1], // 插入
dp[i-1][j-1] // 替换
});
}
}
}
return dp[m][n];
}
实现简单的模糊搜索功能
有了编辑距离函数后，就可以对一组候选字符串进行匹配，找出与目标词足够接近的结果。
void fuzzySearch(const std::vector<std::string>& dictionary,
const std::string& query,
int maxDistance = 2) {
std::cout << "Searching for: " << query << "\n";
std::cout << "Results (distance <= " << maxDistance << "):\n";
for (const auto& word : dictionary) {
int dist = levenshteinDistance(query, word);
if (dist <= maxDistance) {
std::cout << " \"" << word << "\" (distance: " << dist << ")\n";
}
}
}
测试示例：
int main() {
std::vector<std::string> words = {
"apple", "apply", "apples", "banana", "orange",
"application", "applet", "hello", "help"
};
fuzzySearch(words, "appl", 1); // 应该匹配 apple, apply, applet 等
return 0;
}
优化和扩展建议
这个基础版本适合学习和小型应用。实际使用中可考虑以下改进：
- 空间优化：由于 dp 只依赖前一行，可用两个一维数组代替二维数组，降低内存开销。
- 提前终止：如果某行最小值已超过阈值，可提前退出。
- 忽略大小写：比较前统一转为小写。
- 支持通配符或子串匹配：结合 strstr 或正则表达式增强灵活性。
基本上就这些。编辑距离是模糊匹配的基础，理解它之后可以进一步尝试 Damerau-Levenshtein（支持交换操作）、Soundex（按发音匹配）等更复杂的算法。
