数据结构

我们感兴趣的是二进制字符串的数据结构。让S = s s .... s _m是大小为m的二进制字符串。 Shift(S,i)是字符串Si位向左循环移位。也就是说，移位（S，I）= S _我小号_{i + 1的}小号_{I + 2}内容S_米小号内容S _I-1。表明支持一个有效的数据结构：数据结构

为O的empy DS的Init()（1）
Insert(s)插入在O二进制串到DS（| S |^2）
Search_cyclic(s)检查是否O（| s |）中的任何i都有Shift(S,i)。

空间复杂度：O（| S 1 | + | S 2 | + ..... + | S_米 |）其中，S _我是一个如果米串我们已经插入了这么多。

如果我必须找到Search_cyclic（S，I）对一些给我，这是与使用后缀树，只是为O穿越它很简单（| S |）。但是在Search_cyclic中，我们没有给定的i，所以我不知道在给定的复杂度下应该怎么做。 OTOH，Insert通常将O（| s |）插入到后缀树中，在这里给出O（| s |^2）。

来源

2012-01-20 Jenny B

我认为这是作业。如果不是这样，请再次移除作业标签。 –

| s |是什么意思？包含二进制字符串的字符串的大小或DS的大小？ Search_cyclic检查什么？ – Shraddha

| s |是我们在Search_cyclic（s）中搜索的字符串的大小。 Search_cyclic（s）应检查DS中是否存在字符串s的移位字符串。我认为这个想法是使用后缀树，我对Insert（s）有一些影响，它可以在O（| s |^2）中，而通常将字符串插入后缀树只需要O（| s |）。所以我应该做一些聪明的事情，增加回旋余地。 –

所以这里是一个解决方案，我可以向你求婚。复杂程度比他们询问你的要复杂得多，但看起来有点复杂。

保留所有字符串的数据结构将是Trie甚至Patricia tree。在这个树中，每个字符串都要插入所有可能的移位中的最小循环移位（即循环移位所有可能的循环移位，这是最小的按字典顺序排列）。您可以计算线性时间内字符串的最小循环移位，稍后我会给出一个可能的解决方案。现在让我们假设你可以做到这一点。下面是所需的操作将如何实施：

的init（） - 初始化都特里和Patricia树是不变的 - 在这里没有问题
插入（S） - 你计算的最小循环移位S'的s in O（| s |），然后将其插入到O（| s'|）= O（| s |）中的任一数据结构中。这是更好的，则需要复杂
Search_cyclic（S） - 您再计算为O S的最小循环移位（| S |），然后你在帕特里夏或特里检查字符串出现，这又是在O（| s |）中完成

此外，内存复杂度是根据需要的，如果构建Patricia可能会更低。

所以所有剩下的就是exaplain如何找到最小的循环移位。既然你提到后缀树，我希望你知道如何在linear time中构建它。所以诀窍是 - 你将自己的字符串添加到自身中（即，加倍），然后为双倍字符串构造一个后缀树。这对于| s |仍然是线性的所以没有问题。之后，你所要做的就是在这棵树中找到最小长度为n的后缀。这并不难，我相信 - 从根开始，始终遵循当前节点上写有最小字符串的链接，直到累积长度超过| s |。由于字符串翻倍，您将始终能够遵循最小字符串链接，直到您至少累积长度为| s |。

希望此回答有帮助。

来源

2012-01-23 07:57:46

回答

相关问题