在C中匹配(几个)字符串的最有效方法？

Question

我们的系统需要接受来自终端的用户输入并匹配一些已知的关键字字符串(可能是10).

我们没有空间/ computrons来做regexp等,代码需要很小和快速.

现在,令人讨厌的方法是:

   // str is null-terminated, assume we know it's safe/sane here
   if(!strncmp(str,"hello",5)
   {
      do_hello();
   }
   else if(!strncmp(str,"world",5)
   {
      do_world();
   }
   else
   {
      meh(); // Wasn't a match
   }

因此,经过一些谷歌搜索和阅读后,我确信更好的方法是将各种匹配的哈希值预先计算为int,然后只使用case语句:

// Assume hash() stops at NULL
switch(hash(str))
{
   case HASH_OF_HELLO:
      do_hello();
      break;

   case HASH_OF_WORLD:
      do_world();
      break;

   default:
      meh();
      break;
}

我们可以在编译时计算*HASH_OF_match*.这似乎是一种从相对较小的集合中选择字符串的更快/更优雅的方式.

那么 - 这看起来合情合理吗？这样做有明显的问题吗？/任何人都有更优雅的方式吗？

作为一个脚注,这是我今天下午看到的最好看的哈希算法;),归功于丹·伯恩斯坦,它看起来就像手头的工作.

unsigned int
get_hash(const char* s)
{
    unsigned int hash = 0;
    int c;

    while((c = *s++))
    {
        // hash = hash * 33 ^ c 
        hash = ((hash << 5) + hash) ^ c;
    }

    return hash;
}

Answer 1

散列的问题是用户输入的任意字符串可能会生成与您的匹配项相同的散列,并且您将执行错误的操作.对于小到10的搜索集,我只是坚持这种if-else方法.或者使用字符串数组和函数指针数组(假设所有函数具有相同的签名)来选择要执行的函数.

char const *matches[10] = {"first", "second", ..., "tenth"};
void (*fn[10])(void) = {&do_first, &do_second, ..., &do_tenth};

for( i = 0; i < 10; ++i ) {
  if( strcmp( str, matches[i] ) == 0 ) {
    (*fn[i])();
  }
}