1

https://www.interviewstreet.com/challenges/dashboard/#problem/4f802ebfad2a1
私のコードは 6/10 テスト ケースに合格しています。

from collections import Counter
j,k = map(int, raw_input().split())

y = Counter(len(raw_input()) for i in range(j))

saved = {}

def f(x):
    if x in saved:  return saved[x]
    if x<1: return 0
    k = y[x] if x in y else 0
    for i in y:
        k += y[i]*f(x-i)
   saved[x] = k
   return k
x = 0
for i in xrange(1,k+1):
    x+=f(i)

print (x+1)%1000000007

「y」のキーはスーパー ストリングの長さであり、その値はセット「H」でその長さを持つスーパー ストリングの数です。

'saved' はメモ化を処理します。

f(x) は、長さ x のハイパー ストリングを計算します。最後の「for ループ」ですべての値を反復処理します。

x には空の文字列 ('') 以外の結果があるため、x+1

4

2 に答える 2

2

スーパー文字列が他のスーパー文字列の連結である場合、このコードは失敗すると思います。この場合、このコードはいくつかのケースを複数回追加します。例えば：

3 2
a
b
ab

あなたの出力 : 8
右の出力 : 7
"ab" の二重カウント
私自身が質問を試みています。

于 2012-09-25T17:15:36.657 に答える
1

OK、これが私のコードです。あなたのコードをアルゴリズムとして使用しましたが、他のスーパー文字列の連結によって形成されるスーパー文字列を削除しました。問題を投稿していただきありがとうございます。この投稿を見る前の私の元のコードは、ひどく最適ではありませんでした。これをさらに最適化するための提案は大歓迎です。

from collections import Counter
j,k = map(int, raw_input().split())

supers_list = []

for i in range(j):
    supers_list.append(raw_input())

def check_concat(Str_, Sub_Str_):
    if Sub_Str_ == "":
        return False

    for i in supers_list:
        if i == Sub_Str_ and Str_ != Sub_Str_:
        return True
    x = Sub_Str_.startswith(i)
    if x == True:
        if check_concat(Str_, Sub_Str_[len(i):]) == True:
            return True
return False

def filter_():
    tmp = []
    global supers_list
    for i in supers_list:
        if check_concat(i,i) == False:
            tmp.append(i)
    supers_list = tmp

filter_()

y = Counter(len(i) for i in supers_list)

saved = {}

def f(x):
    if x in saved:  return saved[x]
    if x<1: return 0
    k = y[x] if x in y else 0
    for i in y:
        k += y[i]*f(x-i)
    saved[x] = k
    return k
x = 0
for i in xrange(1,k+1):
    x+=f(i)

print (x+1)%1000000007
于 2012-09-26T11:44:05.270 に答える