最长非重叠子字符串

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

例如，串

ABADZEDGBADEZ

最长的重复将是 “坏” 的。顺便说一句，如果没有这样的结果，算法应该警告已经发生了这样的事情。我的猜测是这涉及到后缀树。

我相信这一定已经存在。谢谢您的帮助！

来源

2009-08-24 Brandon Pelfrey

只是curious-有什么业务应用为了这？ – Beth 2009-08-24 17:42:30

这不是一个商业应用程序。这与在歌曲中找到主题有关，并且此时更多的是一个古董，直到我得到一个涉及此项目的项目。 =] – 2009-08-24 17:44:27

由于您将此应用于音乐，因此您可能不会寻找100％的匹配;预计从主题的一个实例到另一个实例的预期差异。你可以试着查找基因序列分析算法 - 这里有很多这样的东西。尝试BLAST或其他比对算法。您也可以尝试WinEPI算法家族以及此特定结果集的各种前缀树实现（这些结果允许在子字符串中存在空位;例如，ABCID和AFBCD都包含ABCD）。实际上我有一篇关于算法的论文，如果您有兴趣，可能值得一看;我需要获得授权，请告诉我。

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

来源：一年或两年研究可比（主题检测）主题。

来源

2009-08-24 17:46:10

如果您可以授予我访问权限，将不胜感激！ – 2009-08-24 18:04:07

我认为他将这个应用于歌词，所以我认为他正在寻找100％的比赛。 – las3rjock 2009-08-24 18:06:09

@Brandon - 我已经申请了许可，我会看看我能做些什么。 @ las3rjock - 不是。例如：我是一个傻男人我是傻，男人实例主题：过去式的愚蠢。字符串不完全匹配。另外，很多歌词有不同的标点符号和不一样的。所以我不确定他是否在寻找完全匹配。 – 2009-08-24 18:08:30

Suffix array是一个很好的解决这个问题的数据结构。

Jon Bentley在Programming Pearls中有这个问题的解决方案。

来源

2009-08-24 17:54:11

在编程珍珠的地方？ – 2009-08-24 20:47:12

@Emil H，** 15.2短语** – 2009-08-25 04:16:35

@Nick我不认为在编程珍珠相同的解决方案可直接应用于此。 “BANANA”的例子给出了两次出现的“ANA”，并且因此与OP所述的条件相反，因此是重叠的。对于非重叠条件可能需要进行一些修改。你说什么？ – 2012-11-11 10:29:35

一个简单的算法是做到这一点：

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

（As刚刚发布的其他回复表明，我在这里描述了一个后缀数组。）

来源

2009-08-24 17:55:06

这仍然相当强悍。我想知道是否有一个更优雅的方法？我相信基于树的方法可以保留结构信息，并提供某种可以快速遍历以提供最长信息的深度信息。 – 2009-08-24 18:00:06

使用适当的排序 - 请参阅后缀数组维基百科文章 - 运行时间在最差情况下为O（n log n），通常更好。迭代是O（n），所以主要是排序成本。至少明显的蛮力将是O（n^2）（比较每个可能的对）。构建树木可能会花费更多的内存，这会对性能产生不利的现实影响（考虑缓存等）。 – 2009-08-24 18:06:48

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

创建一个函数，确定O（n）（其中n是文本的长度）中是否存在长度为k的循环子字符串。这可以通过使用滚动散列（请参阅维基百科Rabin-Karp String Matching Algorithm）以线性时间生成所有n散列并使用散列表/ BST（或地图或字典或任何您的语言称为它）来存储相应的子字符串位置。在将当前散列插入数据结构之前，我们先检查一下是否看过。如果之前已经看到过，我们只需查找生成此散列的索引，并查看相应的子字符串是否为非重叠匹配。

现在，我们可以发现在O（n）的时间A 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在这里，我真的要回去睡觉了:)）

来源

2009-08-24 23:34:51 MAK

最长非重叠子字符串

回答

相关问题