我正在尝试评估不同的子字符串搜索（ala strstr）算法和实现，并寻找一些精心设计的针和干草堆字符串，这些字符串将捕获最坏情况的性能和可能的极端情况错误。我想我可以自己解决它们，但我认为有人必须在某个地方收集大量测试用例......
一些想法和对自己的部分回答：
暴力算法的最坏情况：
a^(n+1) b in (a^n b)^m
e.g. aaab in aabaabaabaabaabaabaab
SMOA 最坏的情况：
就像是yxyxyxxyxyxyxx in (yxyxyxxyxyxyxy)^n。需要进一步细化。我试图确保每次进展只是部分匹配长度的一半，并且最大后缀计算需要最大量的回溯。我很确定我走在正确的轨道上，因为这种类型的案例是迄今为止我发现的实现 SMOA 的唯一方法（这是渐近的）6n+5）比 glibc 的 Two-Way（渐近地）运行得慢2n-m但具有相当痛苦的预处理开销）。
对于基于滚动哈希的最坏情况：
无论字节序列如何，都会导致与针的哈希值发生哈希冲突。对于任何相当快的散列和给定的针，应该很容易构造一个其散列在每个点都与针的散列相冲突的干草堆。然而，同时创建长的部分匹配似乎很困难，这是获得最坏情况行为的唯一方法。当然，对于最坏情况的行为，针必须具有一定的周期性，以及通过仅调整最终字符来模拟散列的方法。
双向的最坏情况：
似乎是非常短的针，具有非平凡的 MS 分解 - 类似于bac- 大海捞针在针的右半部分包含重复的误报 - 类似于dacdacdacdacdacdacdac。该算法变慢的唯一方法（除了 glibc 作者实现得不好之外……）是使外循环迭代多次并重复产生该开销（并使设置开销显着）。
其他算法：
我真的只对算法感兴趣O(1)在太空中并且预处理开销较低，因此我没有过多地研究它们的最坏情况。至少博耶-摩尔（不进行修改使其O(n)）有一个不平凡的最坏情况，它变成O(nm).
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
