我正在寻找在数据结构（插入函数）中存储二进制字符串的最有效方法，然后在获取字符串时我想检查给定字符串的某个循环字符串是否在我的结构中。搜索循环字符串
我想过把输入字符串存储在Trie中，但是当试图确定我现在得到的字符串中是否有一些循环字符串被插入Trie时，意味着要执行| s |在Trie搜索所有可能的循环字符串。
有没有什么办法可以更有效地做到这一点，而地点的复杂性将会像Trie一样？
注：当我说一个字符串，我指的是循环的字符串，例如所有的1011循环字符串是：0111, 1110, 1101, 1011
你能拿出基于以下循环串的进行规范化功能：
这将规范化的等价类的一切（1011，1101，1110，0111）的字典序至少值：0111
0101010101指的是此算法中不会表现良好的一个棘手的实例，但如果你的位大致是随机分布的，那么在实践中对于长字符串应该很好。
然后，您可以根据规范形式进行哈希处理，也可以使用只包含以0开头的空字符串和字符串的trie，并且单个trie运行将回答您的问题。
编辑：
，如果我有一个长度的字符串| S |它可能需要很长时间才能找到最少的字典上的值。实际上需要多少时间？
这就是为什么我说010101....是一个值，它表现不佳。假设字符串的长度为n，最长的1的长度为r。如果这些位是随机分布的，则根据"Distribution of longest run"，最长运行的长度是O（log n）。
找到最长运行的时间是O（n）。您可以使用偏移量而不是缓冲区副本来实现移位，这应该是O（1）。运行次数最差的情况是O（n/m）。
然后，做步骤3中的时间应该是
这导致O（n2）的最坏情况，但是平均情况为O（n +log²n）≅O（n）。
我不明白。假设要存储1100010并且要搜索1001。你的算法如何进行？它能找到子串1100吗？ –
不，它不会解决循环字符串的子字符串，但我在OP中没有看到关于子字符串的任何内容。 –
嗯，我的解释是“检查一些循环..是*在*我的结构”是不同的。也许user550413会澄清。 –
你有n个字符串s1..sn并给出一个字符串t你想知道t的循环排列是否是任何s1..sn的子字符串。你想尽可能有效地存储字符串。我正确理解你的问题吗？
如果是这样，这里是一个解决方案，但运行时间很长：对于给定的输入t，设t'= concat（t，t），用s1..sn中的每个s检查t'以查看如果t'和sm的最长子序列至少为| t |如果| si | = k，| t | = l它运行在O（n.k.l）时间。你可以将s1..sn存储在你想要的任何数据结构中。这还不够，或者你呢？
如果这是一个多于这两个字符的字母表，我会说创建一个散列函数，无论字符值的顺序如何都会生成相同的结果，因此您可以快速消除大多数不匹配。 –
@ C.Evenhuis：不，我只使用二进制字符串。 – user550413
您是否预先做了所有插入操作？或者你混插插入和查找？ – templatetypedef