c - strstr 的优化版本(搜索具有恒定长度)

Question

我的 C 程序有很多 strstr 函数调用。标准库 strstr 已经很快了，但在我的例子中，搜索字符串的长度始终为 5 个字符。我用一个特殊版本替换它以获得一些速度:

int strstr5(const char *cs, const char *ct){    while (cs[4]) {        if (cs[0] == ct[0] && cs[1] == ct[1] && cs[2] == ct[2] && cs[3] == ct[3] && cs[4] == ct[4])            return 1;        cs++;    }    return 0;}

该函数返回一个整数，因为它足以知道 ct 是否出现在 cs 中。在这种特殊情况下，我的函数比标准 strstr 简单且更快，但我很想知道是否有人可以应用一些性能改进。即使是很小的改进也是受欢迎的。

总结:

• cs 的长度 >=10，但除此之外它可以变化。长度之前是已知的(在我的函数中没有使用)。 cs的长度通常为100到200。
• ct 的长度为 5
• 字符串的内容可以是任何内容

---

编辑:感谢您的所有回答和评论。我必须研究和测试想法，看看什么最有效。我将从 MAK 关于后缀 trie 的想法开始。

Answer 1

有几个快string search algorithms .尝试查看 Boyer-Moore (正如 Greg Hewgill 已经建议的那样)，Rabin-Karp和 KMP算法。

如果你需要在同一个大文本中搜索许多小模式，你也可以尝试实现一个suffix tree。或 suffix array .但恕我直言，这些在某种程度上更难理解和正确实现。

但请注意，这些技术非常快，但只有在涉及的字符串非常大时才会给您明显的加速。对于长度小于 1000 个字符的字符串，您可能看不到明显的加速。

编辑:

如果您一遍又一遍地搜索相同的文本(即 cs 的值在调用中始终/经常相同)，您将通过使用后缀 trie (基本上是一个 trie 的后缀)。由于您的文本只有 100 或 200 个字符，因此您可以使用更简单的 O(n^2) 方法来构建 trie，然后对其进行多次快速搜索。每次搜索只需要 5 次比较，而不是通常的 5*200 次。

编辑 2:

正如 caf 的评论所提到的，C 的 strstr 算法是依赖于实现的。 glibc 使用线性时间算法，它在实践中应该或多或少与我提到的任何方法一样快。虽然 OP 的方法渐近较慢( O(N*m) 而不是 O(n) )，但它更快可能是因为 n 和 m (模式和文本的长度)都非常小并且它不必在 glibc 版本中进行任何长时间的预处理。