我正在尝试评估不同的子字符串搜索算法和实现,并寻找一些经过精心制作的针和干草堆字符串,以捕获最坏情况下的性能和可能的边角案例错误。我想我可以自己解决这些问题,但我认为某个人必须有一个好的测试用例集合坐在某个地方...
我正在尝试评估不同的子字符串搜索算法和实现,并寻找一些经过精心制作的针和干草堆字符串,以捕获最坏情况下的性能和可能的边角案例错误。我想我可以自己解决这些问题,但我认为某个人必须有一个好的测试用例集合坐在某个地方...
以下是一些想法和部分答案:
暴力算法的最坏情况:
a^(n+1) b
在 (a^n b)^m
中
例如,在 aabaabaabaabaabaabaab
中的 aaab
SMOA 的最坏情况:
类似于 yxyxyxxyxyxyxx
在 (yxyxyxxyxyxyxy)^n
中。需要进一步完善。我试图确保每次前进只有部分匹配长度的一半,并且最大后缀计算需要最大量的回溯。我相当确定我走在正确的轨道上,因为这种类型的情况是我迄今发现的唯一使我的 SMOA 实现(渐近复杂度为 6n+5
)比 glibc 的 Two-Way 运行得更慢的方法(它的渐近复杂度为 2n-m
,但具有适度的痛苦预处理开销)。
基于滚动哈希的任何算法的最坏情况:
无论什么字节序列都会导致与针的哈希值发生碰撞的哈希值。对于任何相对较快的哈希和给定的针,应该很容易构造一个干草堆,其哈希与针的哈希在每个点上发生碰撞。然而,似乎难以同时创建长的部分匹配,这是获取最坏情况行为的唯一方法。自然地,对于最坏情况行为,针必须具有某种周期性,并且可以通过仅调整最终字符来模拟哈希。
Two-Way 的最坏情况:
似乎是非常短的针,具有非平凡的 MS 分解 - 例如 bac
- 其中干草堆包含右半部分组件中重复的误报 - 例如 dacdacdacdacdacdacdac
。这种算法变慢的唯一方法(除了 glibc 作者实现不好之外...)是使外部循环多次迭代并反复发生那种开销(并使设置开销显着)。
其他算法:
我只对空间复杂度为 O(1)
且预处理开销低的算法感兴趣,因此我没有过多考虑它们的最坏情况。至少 Boyer-Moore(没有修改使其成为 O(n)
的修饰)具有一个非平凡的最坏情况,其中它变为 O(nm)
。
虽然没有直接回答你的问题,但你可能会发现这本书《字符串、树和序列算法:计算机科学与计算生物学》中的算法很有趣(包含许多关于子字符串搜索的新颖算法)。此外,它也是一个特殊和复杂情况的良好信息来源。
您可以通过以下方式递归生成容器字符串(或包含的测试值):
从空字符串开始,通过将字母表中的字符添加到左侧或右侧(或两者都添加)来生成集合中当前字符串的增量字符串。
生成容器字符串的字母表由您选择。
您可以测试包含的字符串的2个字母表。一个是组成容器字符串的字母表,另一个是它的补集。