搜索循环字符串

Question

我正在寻找在数据结构中存储二进制字符串的最有效方法(插入函数),然后在获取字符串时我想检查给定字符串的某个循环字符串是否在我的结构中.

我考虑将输入字符串存储在Trie中,但是当我试图确定我现在获得的字符串的某个循环字符串是否插入Trie意味着执行| s | 在Trie中搜索所有可能的循环字符串.

有没有办法更有效地做到这一点,而地方复杂性将像在特里？

注意:当我说一个字符串的循环字符串时,我的意思是例如所有的循环字符串1011是:0111, 1110, 1101, 1011

Answer 1

你能否根据以下内容为循环字符串提出规范化函数:

1. 找到最大的零运行.
2. 旋转字符串,使该行的零位于前面.
3. 对于每个相同大小的零运行,看看旋转到前面是否产生字典上较小的字符串,如果是,则使用它.

这会将等价类(1011,1101,1110,0111)中的所有内容规范化为按字典顺序排列的最小值:0111.

0101010101 是一个棘手的实例,这个算法不会很好地运行,但如果你的位大致是随机分布的,它应该在实践中用于长字符串.

然后,您可以根据规范表单进行哈希,或者使用仅包含空字符串的trie和以0开头的字符串,单个trie运行将回答您的问题.

编辑:

如果我有一个长度为| s |的字符串 找到字典值最小的值可能需要花费大量时间.实际需要花费多少时间？

这就是为什么我说的010101....是它表现不佳的价值.假设字符串的长度为n,最长的1的长度为r.如果比特是随机分布的,则根据"最长运行的分布",最长运行的长度是O(log n).

找到最长跑的时间是O(n).您可以使用偏移量而不是缓冲区副本来实现移位,缓冲区副本应为O(1).运行次数最差情况为O(n/m).

那么,第3步的时间应该是

1. 找到其他长期运行:一个O(n)通过O(log n)存储平均情况,O(n)最坏情况
2. 对于每次运行:O(log n)平均情况,O(n)最坏情况
3.   按字典顺序移位和比较:O(log n)平均情况,因为大多数比较随机选择的字符串早期失败,O(n)最坏情况.

这导致O(n²)的最坏情况,但O(n +log²n)≅O(n)的平均情况.