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]）
返回1;
CS ++;
}
返回0;
}
该函数返回一个整数，因为它足以知道ct中是否出现ct。 在这种特殊情况下，我的function比标准的strstr简单快捷，但我很想知道是否有人可以应用一些性能改进。 即使很小的改进也是受欢
摘要：
- cs的长度> = 10，但不然它可以变化。 之前已知长度（未在我的函数中使用）。 cs的长度通常为100至200。
- ct的长度为5
- 字符串的内容可以是任何内容
编辑：感谢您的所有答案和评论。 我必须研究和测试想法，看看什么效果最好。 我将从MAK关于后缀trie的想法开始。
有几种快速字符串搜索算法 。 试着看看Boyer-Moore （正如Greg Hewgill所建议的那样）， Rabin-Karp和KMP算法。
如果需要在同一大块文本中搜索许多小图案，还可以尝试实现后缀树或后缀数组 。 但这些是恕我直言，有点难以理解和正确实施。
但请注意，这些技术非常快，但如果涉及的字符串非常大，则只会给你一个明显的加速。 对于长度小于1000个字符的字符串，您可能看不到明显的加速。
编辑：
如果你一遍又一遍地搜索相同的文本（即cs的值在整个调用中总是/经常是相同的），你将通过使用后缀trie（基本上是一系列后缀）获得大的加速。 由于您的文本小到100或200个字符，您可以使用更简单的O（n ^ 2）方法来构建trie，然后对其进行多次快速搜索。 每次搜索只需要5次比较，而不是通常的5 * 200。
编辑2：
正如caf的评论所提到的，C的strstr算法依赖于实现。 glibc使用线性时间算法，在实践中应该或多或少与我提到的任何方法一样快。 虽然OP的方法渐近变慢（O（N * m）而不是O（n）），但它更快可能是因为n和m（模式和文本的长度）都非常小而且它不必在glibc版本中进行任何长时间的预处理。
减少比较次数将提高搜索速度。 保持字符串的运行int并将其与搜索项的固定int进行比较。 如果匹配则比较最后一个字符。
uint32_t term = ct[0] << 24 | ct[1] << 16 | ct[2] << 8 | ct[3]; uint32_t walk = cs[0] << 24 | cs[1] << 16 | cs[2] << 8 | cs[3]; int i = 0; do { if ( term == walk && ct[4] == cs[4] ) { return i; } // or return cs or 1 walk = ( walk << 8 ) | cs[4]; cs += 1; i += 1; } while ( cs[4] ); // assumes original cs was longer than ct // return failure
添加对短cs的检查。
编辑：
添加了评论中的修复程序。 谢谢。
这可以很容易地用于使用64位值。 您可以将cs [4]和ct [4]存储在局部变量中，而不是假设编译器会为您执行此操作。 您可以在循环之前向cs和ct添加4，并在循环中使用cs [0]和ct [0]。
strstr的界面强加了一些可以打败的约束。 它采用以null结尾的字符串，任何首先对其目标进行“strlen”的竞争者都将失败。 它不需要“状态”参数，因此设置成本不能在（例如）相同目标或模式的许多调用中分摊。 预计可以处理各种输入，包括非常短的目标/模式和病理数据（考虑在“ABABABABAB … C”字符串中搜索“ABABAC”）。 libc现在也依赖于平台。 在x86-64世界中，SSE2已有七年历史了，使用SSE2的libc strlen和strchr比朴素算法快6-8倍。 在支持SSE4.2的Intel平台上，strstr使用PCMPESTRI指令。 但你也可以击败它。
Boyer-Moore（和Turbo BM，以及Backward Oracle Matching等人）的设置时间几乎使它们无法运行，甚至没有计算出以null结尾的字符串问题。 Horspool是受限制的BM，在实践中运作良好，但不能很好地处理边缘情况。 我在该领域发现的最好的是BNDM（“向后不确定性指向 – 非循环 – 词 – 图形匹配”），其实现小于其名称:-)
以下是一些可能感兴趣的代码片段。 智能SSE2击败天真的SSE4.2 ，并处理空终止问题。 BNDM实施显示了一种保持设置成本的方法。 如果您熟悉Horspool，您会注意到相似性，除了BNDM使用位掩码而不是跳过偏移。 我即将发布如何为Horspool和BNDM等后缀算法（有效地）解决null-terminator问题。
所有良好解决方案的共同属性是针对不同的参数长度分成不同的算法。 一个例子是Sanmayce的“Railgun”function 。
如果cs短于4个字符，您的代码可能会访问超出其分配范围的cs 。
字符串搜索的常见优化是使用Boyer-Moore算法，您可以从ct的末尾开始查看cs 。 有关算法的完整说明，请参阅链接页面。
你不会在现代的x86计算机上击败好的实现。
新的英特尔处理器有一条指令，它接受你正在检查的字符串的16个字节，最多16个字节的搜索字符串，并在单个指令中返回哪个是搜索字符串可能的第一个字节位置（或者如果没有）。 例如，如果在字符串“abcdefghijklmnHexyz”中搜索“Hello”，则第一条指令将告诉您字符串“Hello” 可能从偏移量14开始（因为读取16个字节，处理器具有字节H，e，未知，这可能是是“Hello”的位置。从偏移量14开始的下一条指令然后告诉字符串不存在。是的，它知道跟踪零字节。
这是两条指令，用于查找19个字符串中不存在五个字符的字符串。 尝试用任何特殊情况代码打败它。 （显然这是专门为strstr，strcmp和类似指令构建的）。