c++ - 如何更有效地计算 n 个字符串之间的不匹配分数？

Question

假设我有一个包含 n 字符串的 vector ，其中字符串的长度可以是 5...n。每个字符串必须逐个字符地与每个字符串进行比较。如果不匹配，则分数增加 1。如果有匹配，则分数不会增加。然后我会将结果分数存储在矩阵中。

我是这样实现的:

for (auto i = 0u; i < vector.size(); ++i)
{
  // vector.size() x vector.size() matrix
  std::string first = vector[i]; //horrible naming convention
  for (auto j = 0u; j < vector.size(); ++j)
  {
    std::string next = vector[j];
    int score = 0;
    for (auto k = 0u; k < sizeOfStrings; ++k)
    {
      if(first[k] == second[k])
      {
        score += 0;
      }
      else
      {
        score += 1;
      }
    }
    //store score into matrix
  }
}

我对这个解决方案不满意，因为它是 O(n^3)。所以我一直在想其他办法让这个更有效率。我考虑过编写另一个函数来替换 j for 循环的内部结构，但是，它仍然是 O(n^3)，因为该函数仍然需要k 循环。

我也考虑过队列，因为我只关心 string[0] 而不是 string[1] 到 string[n]。 String[1] 与 string[2] 相比 string[n]。 String[2] 与 string[3] 与 string[n] 等相比。所以我的解决方案有不必要的计算，因为每个字符串都在比较到每个其他字符串。这个问题是，我不太确定如何从中构建我的矩阵。

我终于查看了 std 模板库，但是 std::mismatch 似乎不是我要找的，或者 std::find .大家还有什么想法吗？

Answer 1

我认为您无法轻易摆脱 O(n^3) 次比较，但您可以轻松实现您所说的更改。由于比较只需要以一种方式进行(即比较字符串 [1] 和字符串 [2] 与比较字符串 [2] 和字符串 [1] 相同)，正如您所指出的，您不需要迭代每次遍历整个数组，并且可以将内循环的起始值更改为外循环的当前索引:

for (auto i = 0u; i < vector.size(); ++i) {
    // vector.size() x vector.size() matrix
    std::string first = vector[i]; //horrible naming convention
    for (auto j = i; j < vector.size(); ++j) {

要将其存储在矩阵中，请设置您的 i x j 矩阵，将其初始化为全零并将每个分数简单地存储在 M[i][ j]

for (auto k = 0u; k < sizeOfStrings; ++k) {
    if (first[k] != second[k]) {
        M[i][j]++;
    }
}