2

给定一个字符串s，找出时间复杂度最长的双后缀O(|s|)。

示例：对于 string banana，LDS 是na。因为abaabaa它baa。

显然我考虑过使用后缀树，但我很难在其中找到双后缀。

4

2 回答 2

0

我认为 Gene 的解决方案更易于实现，并且由于它不依赖于树状结构而是依赖于阵列，因此它也可能对硬件更友好。

但是既然你提到了后缀树，那么让我们来看看基于后缀树的解决方案吧！我将假设您使用结束标记来标记您在树中插入的字符串的结尾。为了说明这一点，下面是为您的abaabaa示例构建的后缀树的表示：

$ - ##
b a a - $ - ## // Longest double suffix: P is the first dash, N the second
        b a a $ - ## // N' is the dash
a - $ - ##
    a - $ - ##
        b a a $ - ##
    b a a - $ - ##
            b a a $ - ##

当N是后缀树中的一个节点时，我们将表示|N| N表示的子串的长度。

您如何表征后缀树中的“双后缀”？嗯，它是一个终端节点N，其父节点具有特定属性：设P为双后缀的父节点，则：

  • P具有到仅包含字符串的结束标记（上）的后缀节点N的转换。$
  • 让suffix是由节点P表示的子字符串，带有附加的结束标记（baa$在您的示例中）。如果我们使用suffix从P沿着树向下走，我们最终会到达另一个后缀节点N'（实际上不需要沿着树向下走）
  • 节点P表示的子字符串 是双后缀（baa在我们的例子中）。
  • 我们有等式|N'| = 2。|P| + 1和|N| = |P| + 1

鉴于此，您只需遍历后缀节点并测试此条件。如果您按长度递减的顺序迭代后缀，您可能会变得贪婪：第一个匹配项必然是最长的双后缀。

请注意，我们可以在检查了长度为 |S|/2 的后缀后停止搜索，并且只遍历奇数长度的后缀（不要忘记我们在字符串中添加了一个结束标记）

复杂性分析

构建后缀树是O(|S|).
令N'为后缀节点，并N为长度(|N'|-1)/2 + 1的后缀的后缀节点。假设树的构造正确：

  • 后缀可以按递增顺序存储在数组/向量中，因为树的创建以长度递增顺序添加它们（至少使用 Ukkonen 算法）。
  • 因此访问长度为k的后缀是O(1)
  • 访问由树的一个节点表示的子字符串是，O(1)特别是，这适用于N和N '
  • 找出从P到N的转换是否只包含结束标记 ( $) 是O(1)
  • 检查是否|N'| = 2。|P| + 1确实是O(1)

由于我们以长度递减的顺序遍历后缀，因此我们必须关注N'后缀（双后缀，即baabaa$在您的示例中），因此我们只需要：

  • 获取N后缀节点，使得|N'| = 2.|N| - 1：O(1)
  • 获取P后缀节点的父节点N：O(1)
  • 检查从P到N的转换仅包含结束标记$：O(1)

证明：（ 我们在下面的证明中忽略了结束标记）

上面的 3 个步骤，如果导致一个真实的评估，证明存在一个长度为2 的后缀。|P| 以P表示的子字符串开头，它也是一个后缀。由于这个子串是后缀，所以后缀长度为2.|P| 必然以它结尾，因此由该子串 QED 的两次出现组成。

由于我们最多对(|S|/2 + 1)/2后缀执行此步骤，因此识别步骤是O(|S|)最坏的情况。

因此，整体复杂度为O(|S|)。

于 2016-08-03T08:20:46.753 回答
0

反转字符串并构建稀疏数组P[i][j]，其中i是 from 0to log(n)，j是 from 0to n-1，n是字符串的长度。P[i][j]指后缀从 positionj和 length开始的排名2^i。因此，如果P[i][j]=P[i][k]，索引处的后缀的第一个2^i字符j和k相等。

0现在您的问题减少到为（反转字符串的开头）和另一个后缀找到最长的公共前缀index i，例如LCP >= i. 其中 LCP 可以通过简单地使用时间P数组来计算log(n)，通过比较2^x这两个后缀的第一个字符并逐渐减少x.

总复杂度为n*log(n)*log(n)。这是工作 C++ 源代码：https ://ideone.com/aJCAYG

于 2016-07-20T03:52:47.470 回答