一尘不染

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

algorithm

我的弦很长。我想找到此字符串的所有唯一子字符串。我试图在使用 集合
(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位版本之间切换的选项。


阅读 213

收藏
2020-07-28

共1个答案

一尘不染

如果您确实需要内存,则可以尝试制作后缀树。尝试不是奇异的数据结构,因此,对于像Python这样的主流语言,可能有不错的实现,它们可以用于实现后缀树。
Marisa-Trie应该具有良好的内存使用率。

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