如何高效计算n个字符串间的不匹配得分（mismatch score）？

看起来你已经意识到三重循环的性能瓶颈了——当前方案的时间复杂度是O(n²L)（L为字符串长度，你之前说的O(n³)应该是假设L和n同阶的情况），当n和L都较大时确实会很慢。针对这个计算两两字符不匹配数的需求，我给你几个实用的优化思路，从易实现到高性能都有：

1. 先做「无成本」的小优化：利用对称性+避免字符串拷贝 #

首先，你的代码里有两个明显的浪费：一是每次循环都拷贝了字符串（std::string first = vector[i]），二是重复计算了对称位置的得分（比如i和j、j和i的得分完全一样）。先把这两个问题解决，能立刻减少近一半的计算量，还能节省内存开销：

const size_t n = vector.size();
// 初始化矩阵，默认i和自己的得分为0
std::vector<std::vector<int>> matrix(n, std::vector<int>(n, 0));

for (size_t i = 0; i < n; ++i) {
    // 用引用直接访问原字符串，避免不必要的拷贝
    const std::string& str_i = vector[i];
    // 只计算i < j的情况，利用对称性填充j < i的位置
    for (size_t j = i + 1; j < n; ++j) {
        const std::string& str_j = vector[j];
        int score = 0;
        // 直接判断字符不相等的情况，比先判断相等再加0更高效
        for (size_t k = 0; k < str_i.size(); ++k) {
            if (str_i[k] != str_j[k]) {
                score++;
            }
        }
        matrix[i][j] = score;
        matrix[j][i] = score;
    }
}

这个优化没有改变时间复杂度的阶，但实际运行速度能提升40%-50%，而且实现起来完全不需要额外依赖，属于「立竿见影」的优化。

2. 并行化：把多核CPU的算力用起来 #

如果你的机器是多核CPU，可以用OpenMP把外层循环并行化，让多个核心同时计算不同的i对应的得分，这能带来和核心数成正比的性能提升（比如8核CPU能有5-7倍的速度提升）：

#include <omp.h>

const size_t n = vector.size();
std::vector<std::vector<int>> matrix(n, std::vector<int>(n, 0));

// 并行化外层循环，注意确保矩阵的访问是线程安全的（这里因为每个i只处理自己的行，所以没问题）
#pragma omp parallel for shared(matrix, vector)
for (size_t i = 0; i < n; ++i) {
    const std::string& str_i = vector[i];
    for (size_t j = i + 1; j < n; ++j) {
        const std::string& str_j = vector[j];
        int score = 0;
        for (size_t k = 0; k < str_i.size(); ++k) {
            if (str_i[k] != str_j[k]) {
                score++;
            }
        }
        matrix[i][j] = score;
        matrix[j][i] = score;
    }
}

注意编译的时候需要加上OpenMP的编译选项（比如GCC用-fopenmp）。

3. SIMD向量化：一次比较多个字符 #

如果你的字符串长度比较规整（比如是16/32的倍数），可以利用CPU的SIMD指令集（比如SSE、AVX2）一次比较多个字符，把内层循环的效率提升数倍。比如用AVX2的256位寄存器，一次可以比较32个ASCII字符：

#include <immintrin.h>

// 用AVX2加速计算两个字符串的不匹配数
int count_mismatches_avx2(const std::string& a, const std::string& b) {
    const size_t len = a.size();
    int score = 0;
    // 把字符串指针转成AVX2寄存器指针
    const __m256i* ptr_a = reinterpret_cast<const __m256i*>(a.data());
    const __m256i* ptr_b = reinterpret_cast<const __m256i*>(b.data());
    // 计算可以用AVX2处理的块数（每个块32个char）
    const size_t num_blocks = len / 32;

    for (size_t k = 0; k < num_blocks; ++k) {
        // 逐字节比较相等性，相等的字节会被设为0xFF，不等为0x00
        __m256i cmp_result = _mm256_cmpeq_epi8(ptr_a[k], ptr_b[k]);
        // 把比较结果转成整数掩码，统计相等的字节数
        int equal_mask = _mm256_movemask_epi8(cmp_result);
        // 总字节数减去相等数，就是不匹配数
        score += 32 - __builtin_popcount(equal_mask);
    }

    // 处理剩余的不足32个的字符
    for (size_t k = num_blocks * 32; k < len; ++k) {
        if (a[k] != b[k]) {
            score++;
        }
    }
    return score;
}

// 主循环调用这个函数
int main() {
    const size_t n = vector.size();
    std::vector<std::vector<int>> matrix(n, std::vector<int>(n, 0));

    for (size_t i = 0; i < n; ++i) {
        const std::string& str_i = vector[i];
        for (size_t j = i + 1; j < n; ++j) {
            int score = count_mismatches_avx2(str_i, vector[j]);
            matrix[i][j] = score;
            matrix[j][i] = score;
        }
    }
}

这个方法能把内层循环的速度提升5-10倍左右，适合字符串较长的场景。

4. 去重优化：针对大量重复字符串的场景 #

如果你的vector里有很多重复的字符串，可以先统计每个唯一字符串的出现位置，只计算唯一字符串之间的得分，再根据出现位置填充原矩阵。比如如果只有m个唯一字符串（m << n），计算量会从O(n²L)降到O(m²L)，性能提升非常明显：

#include <unordered_map>

const size_t n = vector.size();
std::vector<std::vector<int>> matrix(n, std::vector<int>(n, 0));

// 第一步：统计每个字符串对应的所有索引
std::unordered_map<std::string, std::vector<size_t>> str_to_indices;
for (size_t i = 0; i < n; ++i) {
    str_to_indices[vector[i]].push_back(i);
}

// 第二步：提取唯一字符串列表
std::vector<std::string> unique_strings;
for (const auto& pair : str_to_indices) {
    unique_strings.push_back(pair.first);
}
const size_t m = unique_strings.size();

// 第三步：计算唯一字符串之间的得分矩阵
std::vector<std::vector<int>> unique_matrix(m, std::vector<int>(m, 0));
for (size_t i = 0; i < m; ++i) {
    const std::string& str_i = unique_strings[i];
    for (size_t j = i + 1; j < m; ++j) {
        int score = 0;
        const std::string& str_j = unique_strings[j];
        for (size_t k = 0; k < str_i.size(); ++k) {
            if (str_i[k] != str_j[k]) {
                score++;
            }
        }
        unique_matrix[i][j] = score;
        unique_matrix[j][i] = score;
    }
}

// 第四步：填充原矩阵
for (size_t i = 0; i < m; ++i) {
    const auto& indices_i = str_to_indices[unique_strings[i]];
    for (size_t j = 0; j < m; ++j) {
        const auto& indices_j = str_to_indices[unique_strings[j]];
        const int score = unique_matrix[i][j];
        // 把所有i组索引和j组索引对应的位置填充得分
        for (size_t idx_i : indices_i) {
            for (size_t idx_j : indices_j) {
                matrix[idx_i][idx_j] = score;
            }
        }
    }
}

总结 #

• 优先做对称性优化+避免字符串拷贝，零成本见效快；
• 多核机器上直接上OpenMP并行化，实现简单且提升显著；
• 字符串较长时用SIMD向量化，能大幅降低内层循环的耗时；
• 有大量重复字符串时，去重后计算能带来质的飞跃。

内容的提问来源于stack exchange，提问作者Sailanarmo