在一个巨大的字符串中找到长重复的子串

Question

我天真地想象我可以构建一个后缀trie,其中我保持每个节点的访问计数,然后计数大于1的最深节点是我正在寻找的结果集.

我有一个非常长的字符串(数百兆字节).我有大约1 GB的RAM.

这就是为什么用计数数据构建后缀trie在空间方面效率太低而无法为我工作.引用维基百科的后缀树:

存储字符串的后缀树通常比存储字符串本身需要更多的空间.

每个边缘和节点中的大量信息使得后缀树非常昂贵,在良好实现中消耗源文本的存储器大小的大约十到二十倍.后缀阵列将此要求降低到四倍,研究人员继续寻找更小的索引结构.

那是维基百科对树的评论,而不是特里.

如何在如此大量的数据中以及在合理的时间内(例如在现代台式机上不到一小时)找到长重复序列？

(一些维基百科链接,以避免人们将它们作为'答案'发布:字符串算法,特别是最长的重复子字符串问题 ;-))

Answer 1

执行此操作的有效方法是创建子字符串的索引,并对其进行排序.这是一个O(n lg n)操作.

BWT压缩执行此步骤,因此它是一个很好理解的问题,并且有基数和后缀(声明O(n))排序实现等,以使其尽可能高效.对于大型文本,它仍然需要很长时间,也许需要几秒钟.

如果你想使用实用程序代码,C++ 比自然语言std::stable_sort()执行得更好std::sort()(并且比C更快qsort(),但出于不同的原因).

然后访问每个项目以查看其公共子字符串与其邻居的长度是O(n).