7

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

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

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

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

4

2 回答 2

6

您能否根据以下内容提出循环字符串的规范化函数：

  1. 找到最大的零运行。
  2. 旋转字符串，使零的运行在前面。
  3. 对于每个大小相等的零，看看是否将其旋转到前面会产生一个字典顺序较小的字符串，如果是，则使用它。

这会将等价类（1011、1101、1110、0111）中的所有内容规范化为字典上的最小值：0111。

0101010101是一个棘手的例子，这个算法不能很好地执行，但如果你的位大致随机分布，它应该在实践中很好地处理长字符串。

然后，您可以根据规范形式进行散列，或使用仅包含空字符串和以 0 开头的字符串的 trie，运行一次 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) 的平均情况。

于 2012-01-20T20:49:19.627 回答
0

你有 n 个字符串 s1..sn，给定一个字符串 t，你想知道 t 的循环置换是否是任何 s1..sn 的子串。并且您希望尽可能有效地存储字符串。我是否正确理解了您的问题？

如果是这样，这是一个解决方案，但运行时间较长：对于给定的输入 t，让 t' = concat(t,t)，检查 t' 与 s1..sn 中的每个 s 以查看是否最长子序列t' 和 sm 至少为 |t| 如果 |si| = k, |t| = l 它在 O(nkl) 时间内运行。您可以将 s1..sn 存储在您想要的任何数据结构中。这够好还是你？

于 2012-01-20T21:27:29.300 回答