如何找到一个很长字符串的所有唯一子字符串？

Question

我有一个很长的字符串。我想找到这个字符串的所有唯一子字符串。我尝试编写代码，其中使用集合（python）来存储所有子字符串以确保唯一性。对于许多中型和大型字符串，我得到了正确的结果，但是在非常大的字符串的情况下，我得到了 MemoryError。我用谷歌搜索了一下，发现python中的set数据结构有很大的 RAM 占用空间，也许这就是我收到 MemoryError 的原因。

这是我的代码：

a = set()
for i in range(n):
    string = raw_input()
    j = 1
    while True:
        for i in xrange(len(string)-j+1):   
            a.add(string[i:i+j])
        if j==len(string):   break
        j+=1
print sorted(list(a))

有没有办法避免大字符串的这个错误？或者有人可以建议对我的代码进行更好的修改来处理这个问题吗？

PS：我没有在 32 位和 64 位版本之间转换的选项。

Answer 1

如果你在内存中确实需要它，那么你可以尝试制作一个后缀树。Tries 不是奇特的数据结构，因此对于像 Python 这样的主流语言可能有很好的实现，它们可用于实现后缀树。 Marisa-Trie应该能够获得良好的内存使用率。

1. 创建一个空的尝试。
2. 对于 [0, len(s)] 中的每个 n，将长度为 n 的后缀添加到 Trie。
3. 从树的根开始的每条路径都是字符串中的一个子字符串，没有这样的路径不是字符串中的子字符串，并且路径是唯一的。