什么是基准测试和压力测试子串搜索算法的好测试用例？

Question

我正在尝试评估不同的子串搜索(ala strstr)算法和实现,并寻找一些精心设计的针和干草堆字符串,它们将捕获最坏情况的性能和可能的角落错误.我想我可以自己解决这些问题,但我认为有人必须在某个地方找到很多测试用例...

Answer 1

一些想法和对自己的部分回答：

暴力算法的最坏情况：

a^(n+1) b在(a^n b)^m

例如aaab在aabaabaabaabaabaabaab

SMOA 最坏的情况：

像yxyxyxxyxyxyxx在(yxyxyxxyxyxyxy)^n. 需要进一步细化。我试图确保每次进展只是部分匹配长度的一半，并且最大后缀计算需要最大量的回溯。我很确定我走在正确的轨道上，因为这种情况是迄今为止我发现的使我的 SMOA 实现（渐近地6n+5）运行得比 glibc 的双向（渐近地但渐进地）慢的2n-m唯一方法。有相当痛苦的预处理开销）。

对于基于滚动哈希的最坏情况：

无论字节序列如何，都会导致与针的哈希值发生哈希冲突。对于任何相当快的散列和给定的针，应该很容易构造一个其散列在每个点都与针的散列相冲突的干草堆。然而，同时创建长的部分匹配似乎很困难，这是获得最坏情况行为的唯一方法。当然，对于最坏情况的行为，针必须具有一定的周期性，以及通过仅调整最终字符来模拟散列的方法。

双向的最坏情况：

似乎是非常短的针，具有非平凡的 MS 分解 - 类似于bac- 大海捞针在针的右半部分包含重复的误报 - 类似于dacdacdacdacdacdacdac。该算法可能会变慢的唯一方法（除了 glibc 作者实施得不好之外......）是使外循环迭代多次并重复产生该开销（并使设置开销显着）。

其他算法：

我真的只对O(1)太空中且预处理开销较低的算法感兴趣，所以我没有太多地研究它们的最坏情况。至少 Boyer-Moore（未经修改O(n)）有一个不平凡的最坏情况，它变成O(nm)。

Answer 2

没有直接回答你的问题，但你可能会发现书中的算法 - 字符串、树和序列的算法：计算机科学和计算生物学 - 很有趣（有许多关于子字符串搜索的新颖算法）。此外，它也是特殊和复杂案例的良好来源。