什么是最快的子字符串搜索算法？

好的，为了不让自己听起来像个白痴，我会更明确地陈述问题/要求：

• 需要在C风格的空终止字符串中查找针（模式）和干草堆（文本）。未提供长度信息；如果需要，必须计算。
• 函数应返回第一个匹配项的指针，如果未找到匹配项，则返回NULL。
• 不允许失败情况。这意味着任何具有非常量（或大常量）存储要求的算法都需要具有分配失败的回退情况（并且回退情况的性能有助于最坏情况的性能）。
• 实现应使用C语言，但仅有算法的良好描述（或链接）而无代码也可以。

...以及我所说的“最快”是什么意思：

• 确定性的 O(n)，其中 n 是指 haystack 的长度。（但是如果将其与更健壮的算法结合起来，可以使用通常为 O(nm) 的算法（例如滚动哈希）中的思想，以获得确定性的 O(n) 结果。）
• 从未表现出比朴素的暴力算法更差的性能（可测量的；if (!needle[1]) 等需要一些计时器是可以接受的），特别是在非常短的 needle 上，这可能是最常见的情况。（无条件的重度预处理开销不好，试图通过牺牲常规 needle 的代价来改善病态 needle 的线性系数也不好。）
• 对于任意给定的 needle 和 haystack，在搜索时间上与任何其他广泛实现的算法相比具有可比或更好的性能（搜索时间不超过其他算法的50%）。
• 除了这些条件外，我将“最快”的定义留给开放式的。一个好的答案应该解释为什么你认为你提出的方法是“最快”的。

我的当前实现大约比 glibc 的 Two-Way 实现慢10％到8倍（取决于输入）。

更新：我的当前最佳算法如下：

• 对于长度为1的针，使用strchr。
• 对于长度为2-4的针，使用机器字来一次比较2-4个字节，方法如下：用位移将针预加载到16或32位整数中，并在每次迭代中从干草堆中循环旧字节/新字节。每个干草堆的字节都被读取一次，并产生与0（字符串结尾）和一个16或32位比较的检查。
• 对于长度大于4的针，使用具有坏移位表的双向算法（例如Boyer-Moore），该算法仅应用于窗口的最后一个字节。为避免初始化1kb表的开销，这将是许多中等长度针的净损失，我保留了一个位数组（32字节），标记哪些条目在移位表中已初始化。未设置的位对应于永远不出现在针中的字节值，可以进行完整的针长移位。

我心中的重要问题是：

• 有没有办法更好地利用坏的移位表？Boyer-Moore通过向后扫描（从右到左）最好地利用它，但Two-Way需要从左到右扫描。
• 我找到的唯一两个适用于一般情况（没有内存不足或二次性能条件）的可行算法是Two-Way和String Matching on Ordered Alphabets。但是否存在易于检测的情况，其中不同的算法将是最优的？当然，对于m<100左右，许多O(m)（其中m是针长度）的空间算法都可以使用。如果有一个仅需要线性时间的简单测试针的算法，则还可以使用最坏情况二次的算法。

额外加分项：

• 如果假定针和草堆都是格式良好的UTF-8，您是否可以通过这种方式提高性能？（由于具有不同字节长度的字符，格式良好性在针和草堆之间强加了一些字符串对齐要求，并在遇到不匹配的头字节时允许自动的2-4字节移位。但是，除了各种算法已经给出的最大后缀计算、好后缀移位等之外，这些约束是否会给您带来更多/任何好处？）

注意：我对大多数算法都很熟悉，只是不知道它们在实践中表现如何。这里有一个很好的参考资料，以便别人不再给我关于算法的评论/答案: http://www-igm.univ-mlv.fr/~lecroq/string/index.html