string - 搜索循环字符串

Question

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

我考虑过将输入字符串存储在 Trie 中，但是当尝试确定我现在得到的字符串的某些循环字符串是否插入到 Trie 中时，意味着执行 |s| 操作。在 Trie 中搜索所有可能的循环字符串。

有什么方法可以更有效地做到这一点，而地方的复杂性就像在 Trie 中一样？

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

Answer 1

你能根据以下内容提出一个循环字符串的规范化函数吗:

1. 找到最大的零串。
2. 旋转字符串，使该串零位于前面。
3. 对于每次相同大小的零，查看将其旋转到前面是否会产生按字典顺序排列的较小字符串，如果是，则使用该字符串。

这会将等价类(1011、1101、1110、0111)中的所有内容规范化为字典顺序上的最小值:0111。

0101010101 是一个棘手的实例，该算法将无法很好地执行，但如果您的位大致随机分布，那么它在长字符串的实践中应该可以很好地工作。

然后，您可以根据规范形式进行散列，或使用仅包含空字符串和以 0 开头的字符串的 trie，并且一次 trie 运行将回答您的问题。

编辑:

if I have a string of a length |s| it can take a lot of time to find the least lexicographically value..how much time will it actually take?

这就是为什么我说 010101.... 是一个表现不佳的值。假设字符串的长度为 n，最长的 1 串的长度为 r。如果位是随机分布的，则根据 "Distribution of longest run" ，最长游程的长度为 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)。