我不知道是否有人知道的最长经常不重叠的子字符串（最佳？）算法。
例如，在弦
ABADZEDGBADEZ
最长的重复将是“BAD”。 顺便说一句，如果没有这样的结果，该算法应提醒已发生这样的事情。 我的猜测是，这涉及到后缀树。
我敢肯定，这必须已经存在的地方。 谢谢您的帮助！
Answer 1:
既然你申请这个音乐，你可能不找100个％匹配; 将有从主题到另一个的一个实例可以预期的数据差异。 你可以尝试寻找了基因序列分析算法 - 有很多这种东西品种对那里发生的。 尝试BLAST或者其他比对算法。
你也可以尝试WINEPI家庭的算法，以及这个特定的结果集的各种前缀树实现（这些结果允许在子缺口;例如，ABCID和AFBCD都包含ABCD）。 其实我有一个算法，可能是值得考虑的，如果你有兴趣的论文; 我需要获得分布授权，所以让我知道。
请注意，这实际上是一个非常复杂的问题（有效地完成）大型数据集。
资料来源：研究一两年在可比的（主题检测）的话题。
Answer 2:
后缀阵列是解决这个问题一个很好的数据结构。
还有就是这个问题的解决方案在规划珍珠由乔恩·本特利。
Answer 3:
一个简单的算法是这样做：
- 创建表示字符串切片的数据结构; 实现比较/排序以适合的语言
- 创建开始[首字符，最后一个字符]，[第二个字符，最后一个字符]，高达[最后一个字符，最后一个字符]字符串的每一片的列表
- 这个排序名单 - 为O（n log n）的
- 这带来共同的前缀所有的字符串切片在一起。 然后，您可以遍历列表，比较每对看到在一开始他们有多少个字符共享，如果它比你的最大更大然后采取记录下来，并把它作为新的最大值
（作为刚刚发布的其他应答表示，我在这里介绍一个后缀数组）。
Answer 4:
好了，这是一个疯狂的想法。
创建确定是否存在长度为k的在O（N）的重复子串（其中n是文本的长度）的函数。 这可以通过使用滚动哈希来完成（见维基百科拉宾，卡普字符串匹配算法 ）来产生线性时间所有的n个散列和使用哈希表/ BST（或地图或字典或任何语言调用它）来存储相应的子串的位置。 将当前的散列数据结构前，我们检查，如果我们已经看到它之前。 如果以前已经见过，我们简单地查找其中生成该散列索引，看看相应的子是不重叠的匹配。
现在，我们可以发现在O（n）的时间长度AK子，我们只需运行一个二进制搜索找到我们可以用我们的功能找到一个不重叠的子字符串匹配最大ķ。
在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在这里，我真的要回去睡觉了:)）
文章来源: Longest Non-Overlapping Substring
