2

我正在尝试在hackerrank.com 上编写这个问题：

https://www.hackerrank.com/challenges/find-strings

我的代码在小情况下运行良好，但在大情况下我的字典很快就会耗尽内存。我能做些什么来解决这个问题？我不想使用列表，因为那样检查条目是否已经存在需要很长时间......这是我的代码：

n = int(raw_input())
words = []
for x in range(n):
    words.append(raw_input())
test = int(raw_input())
queries = []
for x in range(test):
    queries.append(raw_input())

dict_of_subwords = {}
for x in words:
    len_of_x = len(x)
    for i in range(len_of_x):
        for j in range(i, len_of_x):
            dict_of_subwords[x[i:j+1]] = 1

list_of_subwords = dict_of_subwords.keys()
list_of_subwords.sort()
for x in queries:
    try:
        print list_of_subwords[int(x)-1]
    except:
        print "INVALID"
4

2 回答 2

0

由于许多关于制作更节省内存的版本的建议，这里有一个版本试图最小化存储量（同时仍然使用相同的算法方法）：

subwords = set()

num_words = int(raw_input())
for i in xrange(num_words):
    word = raw_input()
    for i in xrange(len(word)):
        for j in xrange(i, len(word)):
            subwords.add(word[i:j+1])

subwords = sorted(subwords)

num_queries = int(raw_input())
for x in range(num_queries):
    query = raw_input()
    try:
        print subwords[int(query)-1]
    except:
        print "INVALID"
于 2013-03-19T02:48:43.173 回答
0

你必须使用后缀数组，wiki

python中的后缀数组实现：

后缀数组与后缀树密切相关：

  • 可以通过执行后缀树的深度优先遍历来构造后缀数组。如果边按其第一个字符的字典顺序访问，则后缀数组对应于在遍历期间按访问顺序给出的叶标签。
  • 通过使用后缀和 LCP 数组的组合，可以在线性时间内构建后缀树。有关算法的描述，请参阅 LCP 阵列文章中的相应部分。
于 2014-02-06T11:00:49.960 回答