C++ 字符串比较算法

Question

你最好的字符串比较算法是什么？

我找到 O（n）

#include <string>
bool str_cpmr(char* str1, char* str2)
{
    int l1 = strlen(str1), l2 = strlen(str2) ;          
    if(l1 != l2)
        return false;
    for(int i = 0 ; i < l1 ; i++)
        if(str1[i] != str2[i])
            return false ;
    return true ;
}

我想知道是否有其他/更好的解决方案。

另外，如何准确测试？

我建议比较

• 100 场比赛
• 100 个字符串相差一个字符交换

还有更多要测试字符串比较吗？

它在STL C ++（SLT字符串：：比较）中如何？

谢谢！！！！！

Answer 1

你的函数是 O（n），但仍然需要大约两倍的时间——strlen遍历字符串以找到长度，然后（假设它们的长度相同）你再次遍历字符串比较字符。

取而代之的是，我会遍历琴弦，直到你到达不匹配或两个琴弦的末尾。如果达到不匹配，则返回 false。当且仅当您（同时）到达两个字符串的末尾而没有任何不匹配时，您才返回 true。

Answer 2

从逻辑上讲，很难看出如何在不到 O（n） 的时间内检查字符串中的所有值是否存在单个字符不匹配 - 假设您没有关于该字符串的其他信息。

如果这是一个真正的应用程序，并且您对 strngs 和差异类型有一些了解，如果您知道它包含长度为"N"的序列，例如部分或电话号码，则可以通过首先检查每个第 N 个字符来平均做得更好。

编辑：请注意，这仍然是O（n），O（）仅描述了缩放的力量，它只是O（n/N），它仍然是O（n）。如果将字符串延长 10 倍，则检查每个第 N 个条目仍然需要 10 倍的时间。

Answer 3

您最好的字符串比较算法是什么？

template< class T, class Alloc > bool operator==( basic_string<T,Alloc>& lhs, basic_string<T,Alloc>& rhs ); .

它仅使用源代码的两个字符来比较两个字符串：

a==b;

---

这是一个非智能的答案，用C写成：

bool str_cpmr(char* str1, char* str2)
{
  while( *str1 && *str2 && *str1++ == *str2++ )
    ;
  return *str1 == *str2;
}

它

正好是一个循环，所以它显然是 O（n），其中 n 作为较短字符串的长度。此外，它可能会编译为正好 2n 个内存提取。你可以使用专门的字符串指令走得更快（所以调用 strcmp（） 可能会比这更快），但在直接 C 中你可能不会更快。

Answer 4

改进后的函数可能如下所示：

bool str_cpmr(char* str1, char* str2)
{
    if (NULL == str1 || NULL == str2) return false;
    while (*str1 && *str2) {
        if (*str1++ != *str2++) {
            return false;
        }
    }
    return *str1 || *str2 ? false : true;
}

Answer 5

如果没有关于字符串性质的其他信息，没有什么比 O（n） 更好的了，其中 n 是（较短的）字符串的长度。

你不能做少于n个比较！给我一个可以通过 n-1 比较来做到这一点的算法。然后，字符串中必须有一个位置，算法无法判断字符是否不同。这样我就可以给你一个例子，其中你的算法与n-1比较失败。

您只能通过恒定因子来改善这一点。这还将考虑其他信息，例如，如果您知道底层硬件比较 32 位值的速度比 8 位值快，那么最好比较四个字符的块，而不是逐个字符比较。你不会做得更好。