最长非重叠子串

Question

我想知道有没有人知道最长重复非重叠子字符串的（最优？）算法。

例如，在字符串

ABADZEDGBADEZ

中，最长的重复子字符串是“BAD”。顺便说一下，如果不存在这样的结果，算法应该提示发生了这样的事情。我猜这涉及到后缀树。

我相信这种算法肯定已经存在了。感谢您的帮助！

- Brandon Pelfrey

---

只是好奇- 这个有什么商业应用？ - Beth

这不是一个商业应用程序。它与在歌曲中找到主题有关，目前更像是一件珍品，直到我开始涉及此类项目为止。 =] - Brandon Pelfrey

Answer 1

后缀数组是解决该问题的一种好的数据结构。

《编程珠玑》（作者：乔恩·本特利）中有解决此问题的方案。

- Nick Dandoulakis

---

@Nick 我认为《编程珠玑》中的同样解决方案不能直接应用于这里。 "BANANA" 的例子给出了“ANA”，它出现了两次，因此是重叠的，与 OP 提到的条件相反。可能需要进行一些修改以满足不重叠的条件。你怎么看？ - Abhijeet Kashnia

@AbhijeetKashnia，你是对的。也许我们可以通过确保相邻元素的比较在字符偏移重叠时停止，而不是比较整个字符串来解决这个问题。 - Nick Dandoulakis

Answer 2

由于您将此应用于音乐，因此您可能并不需要完全匹配；从一个主题实例到另一个主题实例可能会存在预期差异。可以尝试查找基因序列分析算法 - 这种类型的内容有很多。尝试使用BLAST或其他对齐算法。

您还可以尝试使用WinEPI系列算法，以及这个特定结果集的各种前缀树实现（这些结果允许子字符串中存在间隙；例如，ABCID和AFBCD都包含ABCD）。如果您感兴趣，我实际上有一篇论文介绍了一个值得研究的算法；但我需要获得发布授权，请告诉我。

请注意，对于大型数据集来说，这实际上是非常复杂的主题（要高效地实现）。

来源：一两年的研究，涉及类似的（主题检测）主题。

- Walt W

---

如果你可以授权给我访问权限，将不胜感激！ - Brandon Pelfrey

我认为他正在将此应用于歌词，因此我认为他正在寻找100％的匹配。 - las3rjock

@Brandon - 我已经请求了权限，我会尽力而为。@las3rjock - 不完全是这样。例如： 我是个傻瓜 我很傻，伙计示例主题：过去时的愚蠢。字符串不是完全匹配的。此外，许多歌词有不同的标点符号等等。所以我不确定他是否在寻找完全匹配。 - Walt W

格式化问题。例如，“我是个傻瓜”与“我很傻，伙计”。 - Walt W

@Brandon - 结果没有分发条款，所以今晚我会发布链接 :) - Walt W

Answer 3

一个简单的算法是这样的：

• 创建一个表示字符串片段的数据结构；根据语言实现比较/排序
• 创建一个包含从[first-character，last-character]开始的每个字符串片段的列表，直到[last-character，last-character]
• 对此列表进行排序-O（n log n）
• 这将把所有具有共同前缀的字符串片段放在一起。然后，您可以遍历列表，比较每对字符串，看它们在开头共享多少个字符，如果大于您的最大值，则记录下来并将其设置为新的最大值

（正如其他回复所示，我在描述后缀数组。）

- Barry Kelly

---

这仍然是一种相当暴力的方法。我在想是否有一种稍微更优雅的方法？我相信基于树的方法将保留结构信息并提供某种深度信息，可以快速遍历以提供最长长度信息。 - Brandon Pelfrey

通过适当的排序 - 参见后缀数组维基百科文章 - 最坏情况下的运行时间为O(n log n)，通常更好。迭代是O(n)，因此被排序成本所支配。显然的暴力算法至少会是O(n^2)（比较每对可能的元素）。构建树可能会消耗更多的内存，这将对性能产生不利的现实影响（考虑缓存等因素）。 - Barry Kelly

Answer 4

好的，这里有一个疯狂的想法。

创建一个函数，确定在O(n)（其中n是文本长度）中是否存在长度为k的重复子字符串。这可以通过使用滚动哈希（参见维基百科Rabin-Karp字符串匹配算法）在线性时间内生成所有n个哈希值，并使用散列表/BST（或映射或字典或您语言所称的任何内容）存储相应的子字符串位置来完成。在将当前哈希插入数据结构之前，我们检查是否以前见过它。如果以前见过，我们只需查找生成此哈希的索引，并查看相应的子字符串是否为非重叠匹配。

现在，我们可以在O(n)时间内找到k长度的子字符串，然后简单地运行二分搜索，以找到我们可以使用我们的函数找到非重叠子字符串匹配的最大k。

以下是Python代码

A=23
MOD=10007 # use a random value in the real world

def hsh(text):
    return sum([ord(c)*A**(len(text)-i-1) for i,c in enumerate(text)])%MOD

def k_substring(text, k):
    substrings={}
    cur=hsh(text[:k])
    pwr=(A**(k-1))%MOD
    substrings[cur]=[0]
    for i in xrange(k,len(text)):
        to_remove=(ord(text[i-k])*pwr)%MOD
        to_add=ord(text[i])
        cur-=to_remove
        if cur<0:
            cur+=MOD
        cur=(cur*A)%MOD
        cur=(cur+to_add)%MOD
        if cur in substrings:
            lst=substrings[cur]
            for index in lst:
                if index+k<=i-k+1 and text[index:index+k]==text[i-k+1:i+1]:
                    return index
            lst.append(i-k+1)
        else:
            substrings[cur]=[i-k+1]
    return -1

def longest_substring(text):
    hi,lo=len(text),0
    while hi>lo:
        mid=(hi+lo+1)>>1
        if k_substring(text,mid)==-1:
            hi=mid-1
        else:
            lo=mid
    index=k_substring(text,lo)
    return text[index:index+lo]

抱歉如果这不太清楚。现在是早上6:30，我真的需要回去睡觉：）

- MAK