strstr 的优化版本（搜索具有恒定长度）

我的 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 更简单、更快，但我很想听听是否有人有一些可以应用的性能改进。即使是很小的改进也是受欢迎的。

Summary:

• cs 的长度 >=10，但其他方面可能会有所不同。长度之前已知（在我的函数中未使用）。 cs的长度通常为100到200。
• ct 的长度为 5
• 字符串的内容可以是任何内容

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

有几个快的字符串搜索算法。尝试看看博耶-摩尔（正如 Greg Hewgill 已经建议的那样），拉宾-卡普 and KMP算法。

如果您需要在同一大段文本中搜索许多小模式，您还可以尝试实现后缀树 or a 后缀数组。但恕我直言，这些有点难以理解和正确实施。

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

EDIT:

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

Edit 2:

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