基准测试和压力测试子串搜索算法有哪些好的测试案例？
我试图评估不同的子字符串搜索（ala strstr）算法和实现，并寻找一些制作精良的针和干草堆字符串，以便捕捉最坏情况的性能和可能出现的角落错误。 我想我可以自己解决这个问题，但是我认为有人必须有一个很好的测试用例集合，
对自己的一些想法和部分答案：
蛮力算法的最坏情况：
(a^nb)^m a^(n+1) b
如aaab在aabaabaabaabaabaabaab
SMOA的最坏情况：
喜欢的东西yxyxyxxyxyxyxx在(yxyxyxxyxyxyxy)^n 。 需要进一步改进。 我试图确保每次前进只是部分匹配长度的一半，并且最大后缀计算需要最大量的回溯。 我非常确定自己在正确的轨道上，因为这种情况是我迄今为止发现的使SMOA（这是渐近6n+5 ）的执行速度比glibc的双向运行速度慢的唯一方式是渐近2n-m但有中等痛苦的预处理开销）。
最糟糕的情况是基于滚动哈希的任何事情：
无论字节序列是否与针的散列值产生散列冲突。 对于任何合理快速的散列和给定的针，应该很容易构建一个干草堆，它的散列在每个点都与针的散列相冲突。 然而，似乎很难同时创建长部分匹配，这是获得最坏情况行为的唯一方法。 当然，对于最坏情况行为，针必须具有一定的周期性，并且通过调整最终字符来模拟散列。
双向的最坏情况：
似乎是非常短的MS分解针头 - 像bac一样 - 干草堆在针的右半部分包含重复的假阳性 - 就像dacdacdacdacdacdacdac 。 这种算法可能会很慢（除了glibc作者实现它的不好之处）之外，唯一的方法就是让外部循环迭代多次并反复招致这种开销（并且使设置开销显着）。
其他算法：
我真的只对O(1)在空间中的算法感兴趣，而且预处理开销很低，所以我没有看过他们最糟糕的情况。 至少Boyer-Moore（没有修改使其成为O(n) ）有一个非平凡的最坏情况，它变成O(nm) 。
不直接回答你的问题，但你可能会发现书中的算法 - 字符串，树和序列算法：计算机科学和计算生物学 - 有趣的（有很多关于子字符串搜索的新算法）。 此外，它也是特殊和复杂情况的良好来源。
一个可能提供有趣统计数据的程序，虽然我现在没有时间测试：
对字符串长度进行随机化，然后对该字符串的内容进行随机化，然后在子字符串的偏移量/长度上随机化（可能不在字符串中），然后随机在子字符串上重复（可能根本不会），重复。
链接地址: http://www.djcxy.com/p/85033.html上一篇: What are good test cases for benchmarking & stress testing substring search algorithms?