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 に答える