如何找到一个很长的字符串的所有唯一子？ [英] How to find all the unique substrings of a very long string?

问题描述

我有一个很长的字符串。我想找到这个字符串的所有唯一子。我试着写了code，我用的设置的（蟒蛇）来存储所有的子串，以确保其唯一性。我收到了很多大中型字符串然而，在案件的非常大的字符串，我得到一个的MemoryError正确的结果。我用Google搜索了一下，发现原来的设置的在Python数据结构有一个大的内存占用，也许这就是为什么我收到的MemoryError。

I have a very long string. I want to find all the unique substrings of this string. I tried to write the code where I used a set(python) to store all the substrings to ensure uniqueness. I am getting correct result for many medium and large strings however in case of very large strings, I am getting a MemoryError. I googled a bit and found out that the set data structure in python has a large RAM footprint and maybe thats why I am getting a MemoryError.

下面是我的code：

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))

有没有办法避免这种错误对于大字符串？或者，有谁能够提出一个更好的修改在我的code来处理这个问题呢？

Is there a way to avoid this error for large strings? Or can anybody suggest a better modification in my code to handle this issue?

PS：我DONOT有32位和64位版本之间进行切换的选项

P.S: I donot have an option of shifting between 32 bit and 64 bit versions.

推荐答案

如果你真的需要它在内存中，那么你可以尝试做一个后缀树。尝试不异国数据结构，所以有可能是可用的一个主流语言如Python良好的实现，并且可以将它们用于实施后缀树。 玛丽莎 - 特里应该得到良好的内存使用情况。

If you really need it in memory, then you can try making a suffix tree. Tries are not exotic data structures, so there are probably good implementations available for a mainstream language like Python, and they can be used to implement suffix trees. Marisa-Trie is supposed to get good memory usage.

1. 创建一个空的线索。
2. 对于每个n在[0，len个（S）]，增加长度为n的线索的后缀。
3. 从该线索的根每路径字符串中的一个子，还有一些没有在字符串中的子字符串没有这样的路径，路径是唯一的。

这篇关于如何找到一个很长的字符串的所有唯一子？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！