我有一个很长的字符串。我想找到这个字符串的所有唯一子字符串。我尝试编写使用 set(python) 存储所有子字符串以确保唯一性的代码。对于许多中型和大型字符串,我得到了正确的结果,但是在非常大的字符串的情况下,我得到了 MemoryError。我在 google 上搜索了一下,发现 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))
对于大字符串有没有办法避免这个错误?或者有人可以建议对我的代码进行更好的修改来处理这个问题吗?
P.S:我没有在 32 位和 64 位版本之间切换的选项。
最佳答案
如果内存中确实需要,那么可以尝试做一个后缀树。尝试不是奇特的数据结构,因此可能有适用于主流语言(如 Python)的良好实现,并且它们可用于实现后缀树。 Marisa-Trie应该获得良好的内存使用率。
- 创建一个空的 trie。
- 对于[0,len(s)]中的每一个n,将长度为n的后缀添加到Trie中。
- 从树的根开始的每条路径都是字符串中的一个子串,没有这样的路径不是字符串中的子串,并且路径是唯一的。
关于python - 如何找到一个很长的字符串的所有唯一子串?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23766570/