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

Question

我正在尝试评估不同的子字符串搜索 (ala strstr) 算法和实现，并寻找一些精心设计的 needle and haystack 字符串，它们将捕获最坏情况下的性能和可能的极端情况错误。我想我可以自己解决它们，但我认为有人必须在某个地方收集大量测试用例......

Answer 1

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

暴力算法的最坏情况:

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

例如aaab 在 aabaabaabaabaabaab

SMOA 的最坏情况:

类似于 (yxyxyxxyxyxyxy)^n 中的 yxyxyxxyxyxyxx。需要进一步细化。我试图确保每个进步只是部分匹配长度的一半，并且最大后缀计算需要最大量的回溯。我很确定我在正确的轨道上，因为这种情况是迄今为止我发现的唯一使我的 SMOA 实现(渐近 6n+5)运行速度变慢的方法比 glibc 的 Two-Way(渐近 2n-m 但具有适度痛苦的预处理开销)。

任何基于滚动哈希的最坏情况:

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

双向的最坏情况:

似乎是具有非平凡 MS 分解的非常短的针 - 类似于 bac - 干草堆在针的右半部分包含重复的误报 - 类似于 dacdacdacdacdacdacdac。该算法可能变慢的唯一方法(除了 glibc 作者实现不佳......)是使外部循环迭代多次并反复产生该开销(并使设置开销显着)。

其他算法:

我真的只对空间O(1) 且预处理开销低的算法感兴趣，所以我没有过多研究它们的最坏情况。至少 Boyer-Moore(没有修改使其 O(n))有一个不平凡的最坏情况，它变为 O(nm)。