-1

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

我发现 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 string::compare) 中怎么样？

谢谢！！！！！

4

5 回答 5

4

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

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

于 2012-10-10T16:39:48.663 回答
3

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

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

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

于 2012-10-10T16:38:29.990 回答
3

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

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

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

a==b;

这是一个用 C 语言编写的非 smartalec 答案：

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

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

于 2012-10-10T16:41:15.417 回答
2

您改进的功能可能如下所示：

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;
}
于 2012-10-10T16:46:59.633 回答
2

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

您不能进行少于 n 次的比较！给我一个可以通过 n-1 比较来完成的算法。那么在字符串中一定有一个位置，算法无法判断字符是否不同。这样我可以给你一个例子，你的算法与 n-1 比较失败。

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

于 2012-10-10T16:51:52.190 回答