c++怎么实现一个简单的模糊搜索算法_C++中实现模糊匹配与编辑距离算法-C++-PHP中文网

编辑距离指将一个字符串转为另一个的最少单字符操作次数，常用动态规划实现，通过设定最大允许距离实现模糊搜索。

c++怎么实现一个简单的模糊搜索算法_c++中实现模糊匹配与编辑距离算法

在C++中实现模糊搜索，核心思路是通过计算两个字符串之间的“距离”来衡量它们的相似度。最常用的方法是编辑距离（Levenshtein Distance）算法。它表示将一个字符串转换为另一个字符串所需的最少单字符编辑操作次数（插入、删除、替换）。

什么是编辑距离？

编辑距离可以用来判断两个字符串的相似程度。比如：

"kitten" → "sitting" 的编辑距离是 3
"hello" → "helli" 的编辑距离是 1

距离越小，字符串越相似。我们可以设定一个阈值，比如最大允许距离为2，超过就不算匹配，从而实现模糊搜索。

用动态规划实现编辑距离

使用二维数组 dp[i][j] 表示 str1 前 i 个字符到 str2 前 j 个字符的最小编辑距离。

#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<:vector>> dp(m + 1, std::vector<int>(n + 1));

    // 初始化边界：从空串变成目标串
    for (int i = 0; i 
</int></:vector></string></algorithm></vector></iostream>

实现简单的模糊搜索功能

有了编辑距离函数后，就可以对一组候选字符串进行匹配，找出与目标词足够接近的结果。

Upstream Recon

在与开源项目（如提交PR、Issue或评论）互动前，先对其进行调研。适用于：提交Issue、提交PR或发表评论之前。

下载

void fuzzySearch(const std::vector<:string>& dictionary,
                 const std::string& query,
                 int maxDistance = 2) {
    std::cout 
</:string>

测试示例：

int main() {
    std::vector<:string> words = {
        "apple", "apply", "apples", "banana", "orange",
        "application", "applet", "hello", "help"
    };

    fuzzySearch(words, "appl", 1);   // 应该匹配 apple, apply, applet 等
    return 0;
}
</:string>