6

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

例如，在字符串

阿巴泽德巴德兹

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

我确定这一定已经存在于某个地方。谢谢您的帮助！

4

4 回答 4

5

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

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

于 2009-08-24T17:54:11.720 回答
4

由于您将其应用于音乐，因此您可能不是在寻找 100% 的匹配；从一个主题实例到另一个主题实例之间会出现预期差异。您可以尝试查找基因序列分析算法——那里有很多各种各样的东西。尝试 BLAST 或其他对齐算法。

您还可以尝试 WinEPI 系列算法，以及此特定结果集的各种前缀树实现（这些结果允许子字符串中存在间隙；例如，ABCID 和 AFBCD 都包含 ABCD）。实际上，我有一篇关于算法的论文，如果您有兴趣，可能值得一看；我需要获得分销授权，所以请告诉我。

请注意，对于大型数据集，这实际上是一个非常复杂的主题（要有效地完成）。

资料来源：针对类似（主题检测）主题的一两年研究。

于 2009-08-24T17:46:10.957 回答
1

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

  • 创建一个表示字符串切片的数据结构；根据语言实现比较/排序
  • 创建从 [first-character, last-character], [second-character, last-character] 到 [last-character, last-character] 的字符串的每个切片的列表
  • 排序这个列表 - O(n log n)
  • 这将所有具有公共前缀的字符串切片放在一起。然后，您可以遍历列表，比较每一对以查看它们在开始时共享的字符数，如果它大于您的最大值，则记下它并将其设置为新的最大值

（正如刚刚发布的另一个回复所示，我在这里描述了一个后缀数组。）

于 2009-08-24T17:55:06.367 回答
0

好的，这是一个疯狂的想法。

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

现在我们可以在 O(n) 时间内找到 ak 长度的子字符串，我们只需运行二进制搜索来找到最大的 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-24T23:34:51.627 回答