我天真地想象我可以构建一个后缀trie，其中我保持每个节点的访问计数，然后计数大于1的最深节点是我正在寻找的结果集。
我有一个非常长的字符串（数百兆字节）。我有大约1 GB的RAM。
这就是为什么用计数数据构建后缀trie在空间方面效率太低而无法为我工作。去引用 维基百科的后缀树：
存储字符串的后缀树通常比存储字符串本身需要更多的空间。
每个边缘和节点中的大量信息使得后缀树非常昂贵，在良好实现中消耗源文本的存储器大小的大约十到二十倍。后缀阵列将此要求降低到四分之一，研究人员继续寻找更小的索引结构。
那是维基百科对树的评论，而不是特里。
如何在如此大量的数据中以及在合理的时间内（例如在现代台式机上不到一小时）找到长重复序列？
执行此操作的有效方法是创建子字符串的索引，并对其进行排序。这是一个O（n lg n）操作。
BWT 压缩做了这一步，所以它是一个很好理解的问题，并有基数和 后缀 （声明O（n））排序实现等使其尽可能高效。对于大型文本，它仍然需要很长时间，也许需要几秒钟。
如果要使用实用程序代码，C ++ std::stable_sort() 施行 许多 比...更好 std::sort() 对于自然语言（并且比C语言快得多） qsort()，但出于不同的原因）。
然后访问每个项目以查看其公共子字符串与其邻居的长度是O（n）。
您可以查看基于磁盘的后缀树。我找到了这个 后缀树实现库 通过谷歌，以及一些可以帮助自己实现它的文章。
你可以用分而治之来解决这个问题。我认为这应该与使用trie的算法复杂度相同，但实现方式可能效率较低
void LongSubstrings(string data, string prefix, IEnumerable<int> positions)
{
Dictionary<char, DiskBackedBuffer> buffers = new Dictionary<char, DiskBackedBuffer>();
foreach (int position in positions)
{
char nextChar = data[position];
buffers[nextChar].Add(position+1);
}
foreach (char c in buffers.Keys)
{
if (buffers[c].Count > 1)
LongSubstrings(data, prefix + c, buffers[c]);
else if (buffers[c].Count == 1)
Console.WriteLine("Unique sequence: {0}", prefix + c);
}
}
void LongSubstrings(string data)
{
LongSubstrings(data, "", Enumerable.Range(0, data.Length));
}
在此之后，您需要创建一个实现DiskBackedBuffer的类，使其成为一个数字列表，当缓冲区达到一定大小时，它会使用临时文件将自身写入磁盘，并在读取时从磁盘中调用从。
回答我自己的问题：
鉴于长匹配也是短匹配，您可以通过首先找到较短的匹配然后查看是否可以“增长”这些匹配来交换RAM的多个传递。
对此的文字方法是在数据中构建一些固定长度的所有序列的trie（在每个节点中具有计数）。然后，您将剔除与您的条件不匹配的所有节点（例如，最长匹配）。然后进行后续的数据传递，将trie构建得更深，但不是更广泛。重复，直到找到最长的重复序列。
一位好朋友建议使用哈希。通过从每个字符开始散列固定长度字符序列，您现在遇到了查找重复哈希值的问题（并验证重复，因为哈希是有损的）。如果为数组分配一个数据长度来保存哈希值，你可以做一些有趣的事情，例如：要查看匹配是否比数据的固定长度传递更长，您可以只比较哈希序列而不是重新生成它们。等等。
那个简单的程序怎么样：
S = "ABAABBCCAAABBCCM"
def findRepeat(S):
n = len(S)
#find the maxim lenth of repeated string first
msn = int(floor(n/2))
#start with maximum length
for i in range(msn,1,-1):
substr = findFixedRepeat(S, i)
if substr:
return substr
print 'No repeated string'
return 0
def findFixedRepeat(str, n):
l = len(str)
i = 0
while ((i + n -1) < l):
ss = S[i:i+n]
bb = S[i+n:]
try:
ff = bb.index(ss)
except:
ff = -1
if ff >= 0:
return ss;
i = i+1
return 0
print findRepeat(S)
这个文字有单词吗？然后我怀疑你想要一个关键词在上下文中的变体：为一行中的n个单词复制每行n次，打破每个单词的每一行;排序整个事物的阿尔法;寻找重复。
如果它是一个长的鸣响字符串，比如说生物信息学DNA序列，那么你想在磁盘上构建像你的trie;为每个字符构建一个记录，并为下一个节点创建磁盘偏移量。我看看第3卷 克努特，第5.4节，“外部分类”。
你可以通过构建一个来解决你的问题吗？ 后缀数组 代替？否则，您可能需要使用其他答案中提到的其中一个基于磁盘的后缀树。
只是一个迟来的想法发生在我身上......
取决于您的操作系统/环境。 （例如64位指针＆mmap（）可用。）
您可以通过mmap（）在磁盘上创建一个非常大的后缀树，然后在内存中保留该树的最常访问的缓存子集。
最简单的方法可能就是 100美元 一堆更多的RAM。否则，您可能必须查看磁盘支持的结构以保存后缀树。