string - 找出是否存在两个相邻的相同子串

Question

我们有一个字符串。

宝 Paypal 贝

现在我们必须检查是否存在一个子字符串，其后跟另一个与第一个子字符串完全相同的子字符串。

在这个例子中: ABEAABABEABE
ABE 后跟 ABE，这是两个相同的子串。

在这个例子中:

AAB

它会是简单的 A，因为 A 后面跟着另一个 A。

在这个例子中:
ABCDEFGHIJKLMNO
不存在这样的子字符串，所以答案是否定的。

我只设法找到一个可以在 O(n^2) 中运行的算法。那就是获取哈希及其前缀。然后对于每个字母，我们简单地扩展并检查以该字母结尾的所有单词。有n个字母。我们需要把它扩大n倍。所以它是 O(n^2)。我相信应该有一个 O(n log n) 的算法来解决这个问题。

有没有人有更好的主意？

Answer 1

我猜您想要遵循此模式的最长子字符串。

首先要做的是构建输入字符串的后缀树。使用Ukkonen's algorithm ，这是 O(n)。

现在，您提供的条件如何在后缀树中翻译？首先，您正在寻找一个重复的子串 ^[1]。 重复的子串 将作为后缀树的内部节点出现。 The maximum number of nodes在从 n-char 字符串构建的后缀树中是 2n - 1。

您可以构建一个包含此类重复子字符串的最大堆，使用它们的长度(字符数)。 您不保留长度大于N/2的子串(参见[1])。这是 O(N)，其中 N 是后缀树的内部节点数。对于任何后缀树:

0 ≤ N ≤ n - 2

现在，您从优先级队列中取出最大值并处理您获得的内部节点i:

1. 令S_i 为与i 相关的子串，k = 0 且curnode = 我
2. 虽然 k < 长度(S_i)
   1. 如果从 i 到 i 的 child 的 key 等于 S_i[k]，然后k = k+1
   2. 否则打破循环。
3. 如果 k == length(S_i)，则子串匹配。否则，您继续下一个子字符串。

复杂性总结​​

令n 为查询字符串的长度。

• 构建后缀树:O(n)
• 构建重复子串的最大堆:[3]
  • 识别重复的子字符串(即内部节点)并将它们存储在数组中:O(n)
  • 堆化数组:O(n)
• 找到最佳匹配:O(n².log(n)) ^[2]

因此，最坏情况下的总体复杂度是以上各项的总和，并且是 O(n².log(n))。

注意事项

我做了上面的算法...因此它不是最优的，如果你足够勇敢，你可以通过this paper描述了一个线性时间算法!无论如何，后缀树是解决这个问题的关键，所以我建议您彻底研究它们。

[1]:警告，重复的子字符串可能部分重叠!

[2]:实际上，最坏情况的复杂度比这个非常朴素的上限要好，但我不知道如何证明它(还？!)。例如，如果有 n - 2 个内部节点，则意味着原始字符串由 n 个相同字符组成。在这种情况下，我们检查的第一个子字符串是匹配项 => 它是 O(n.log(n))。

[3]:如果我们用常规排序替换堆构造 (O(n.log(n)))，最后的比较步骤在 < em>O(n²) 而不是 O(n².log(n)) ... 降低 O(n.log(n))(由于排序步骤)和 O(n²)。