python - 如何降低最长重复序列的复杂度

Question

上周，我接受了亚马逊的采访。面试官问了一个问题，找出 banana 中最长的重复子串如果我们查看字符串 banana，我们会看到 ana(重复 2 次)是一个重叠的重复字符串。我能够找到解决方案，但我的最终输出是错误的。不管怎样，他说这种方法的复杂度是 O(n^2)，这是对的。面试后我更正了我的代码，现在它给出了正确的输出。但是我在整个互联网上搜索了如何降低复杂性。我找不到它。您能否帮助我降低复杂性或任何我可以遵循的引用以降低复杂性。

mystring = "banana"
temp = ""
arr = {}
for i in range(len(mystring)):
    for j in range(i, len(mystring)):
        temp += mystring[j]
        try:
            arr[temp] += 1
        except:
            arr[temp] = 1
    temp = ""
temp = 0
finalstr = ""
for k, v in arr.iteritems():
    if len(k) > 1:
        if temp < v and len(finalstr) < len(k):
            temp = v
            finalstr = k
print finalstr

Answer 1

使用suffix trees 可以在线性时间 O(N) 内解决该问题.后缀树是包含给定文本的所有后缀的树。此外，它们需要花费 O(N) 的时间和空间来构建。

树的边缘标有文本的子字符串。维基百科页面方便地提供了单词 banana 的后缀树:

如果您从根部开始往下看，您会发现所有可能的 banana 后缀。

注意:如果你考虑一下，所有足够的长度之和是 1+2+3+...+N = N*(N-1)/2= O(N^2)!诀窍是你实际上并没有用字符串标记边缘。你的文本 T 是一个字符串，你使用两个索引 i 和 j 来识别它的子字符串，所以当你想读取标签时在一条边上，您转到索引 i 并读取到 j。

现在的想法是，如果一个字符串在文本中重复出现，如 banana 中的 ana ，那么该字符串就是两个不同后缀的前缀:

banana
 | |
 +-+--  prefix of suffix: anana
   |--  prefix of suffix: ana

所以我们从后缀树的根开始，我们读到a然后我们往左边走，然后我们读到NA然后我们往右边走。如您所见，我们最终到达的节点有两个子节点:

• 向左我们读到 $，即字符串结尾，这意味着我们读到了后缀 ana
• 向右走，我们读到 na$，这意味着我们读到了后缀 anana。

注意:这适用于任何 重复的子字符串。所以每一个重复的子串对应一个分支节点。

因此，从根到最深 分支节点的标签将始终形成最长 重复子序列。要找到这个节点，您只需访问树一次即可。

要构建后缀树，最著名的算法是 Ukkonnen，您可能会发现它 described in this article .该算法本身并不平凡。

---

我还想对您的解决方案添加一些评论。

首先:您应该永远不要使用裸except: 而不指定您要捕获的异常类型。例如，您当前的代码可能会阻止用户使用 Ctrl+C 中断它，因为 except: 会捕获 KeyboardInterrupt 异常。在以后的面试中，请记住将 except ExceptionType 与您需要的最具体的异常类型一起使用(在本例中为 except KeyError:)。

其次，collections 模块提供了一个 Counter 类，它专门用于计数，因此您可以像这样简单地重写代码:

from collections import Counter

length = len(mystring)
counts = Counter(mystring[i:j] for i in range(length) for j in range(i, length))

print(max(counts, key=lambda x: (counts[x] >= 2, len(x))))