这样的字符串匹配的最佳方式是什么?

看一看 Ragel . 及AT Mongrel 用于现实世界。尽管我发现用Ragel括起来的邮件解析示例也是一个有趣的小例子,可以进行实验。

不过,根据您的协议,只需检查第一个字节就可以得到一个后续的memcmp(),以验证您的动词是否确实是正确的。C、L、G都是不同的值。

如果常量字符串的数量有限,您可以手工编写自己的“dfa”。只需检查第一个字符。如果它是一个“c”,并且数组中以“c”开头的唯一字符串是“cut”,那么您可以提前中断,因为您已经完成了。如果有两个以c开头的字符串,请检查第二个字符等。如果有大量可能的字符串,这显然不是一个好的解决方案。

有一个gnu c regex库可能就是您想要的。我可能会建议您多学一些关于使用更简单语言(如Perl或Python)的正则表达式的知识,然后当您对Reg感到满意时再学习C库。总的来说是前任。

另外,我也不明白你为什么说memcpy。你是说memcmp吗?你为什么用它来代替strcmp?

您可以做的一件事是让您的程序在启动时迭代您的命令字符串列表,并使用它们构建一个查找树。然后,在运行时,您可以通过在树下导航、在每个节点根据字符串中的下一个字母选择下一个子节点来执行有效的查找,直到您到达一个叶节点(在这种情况下,您有匹配项)或到达一个死端(下一个字母没有子节点),并且您知道没有匹配项。

(构造树很容易——它与查找算法几乎是相同的算法,只是当您没有为下一个字母找到子节点时,您创建一个并将其添加到当前节点,然后继续)

我喜欢 ternary search trees 对于此应用程序。查找时间为o(m),其中m是输入字符串的长度。

还有一篇关于这个数据结构的有帮助的文章 here .

另一种方法

如果字符串是4个ASCII字符或更短的字符,可以将它们存储在32位整数中,然后使用switch语句进行常量时间比较。如果您能够使用64位整数,那么最多可以比较8个ASCII字符。

将字符串的前四个字符表示为整数的函数可能如下所示:

#include <inttypes.h>

uint32_t str_as_int(const char* s) {
  uint32_t n = 0;
  int i;
  for (i = 0; s[i] != '\0' && i < sizeof(uint32_t); i++)
    n |= s[i] << (24 - i * 8);
  return n;
}

嗯,是的,在处理字符串时不应该使用memcpy()或任何mem()函数。为什么?well string函数考虑终止空字符,因为前者更像是字节的原始副本。处理字符串时,始终使用string.h函数。

我将首先使用非常简单的算法,你拒绝失控。先让它工作,然后快点。如果我发现我真的需要专注于我系统中特定的微小部分进行优化,我会选择做一些和明显的解决方案几乎一样简单的事情,但要做一个数量级或更快的事情。

最明显的是用26个候选字符串列表替换一个候选字符串列表。你可能已经猜到了,26是字母表中的字母数,现在候选列表中的每个字符串都以相同的字母开始。查看邮件的第一个字母,然后使用快速查找表选择适当的候选人列表。因此,如果您的第一个字母是“C”,搜索候选人列表“复制”、“剪切”、“关闭”。

如果速度不够快的话,我会认真考虑一些重量级的解决方案,但我怀疑这种事情到底需要多久。