0

私はInterviewStreetでこの課題を解決しようとしています：https ：//www.interviewstreet.com/challenges/dashboard/#problem/4edb8abd7cacd

私はすでに動作するアルゴリズムを持っていますが、そのパフォーマンスを改善したいと思います。その方法について何か提案はありますか？

# Enter your code here. Read input from STDIN. Print output to STDOUT
N = gets.to_i
words = []

while words.length < N do
  words << gets.sub(/\\n$/, '').strip
end 

words.each do |word|
  count = 0
  (word.length).times do |i|
    sub = word[i..-1]
    j=0
    while j < sub.length && sub[j] == word[j] do
      count += 1 
      j+=1
    end
  end
  puts count
end

ありがとう、グレッグ

4

1 に答える 1

3

最悪の場合、アルゴリズムは2次式になります。ほとんどの通常の単語では、2次の動作はなく、十分に機能します（その単純さのために、最悪の場合の動作が優れたより高度なアルゴリズムよりもおそらく高速に実行されます）。

線形の最悪の場合の動作を伴う1つのアルゴリズムは、Zアルゴリズムです。私はあまりルビーを話さないので、当分の間、Pythonバージョンは次のことを行う必要があります。

def zarray(str):
    Z = [0]*len(str)
    Z[0] = len(str)
    left, right, i = 0, 0, 1
    while i < len(str):
        if i > right:
            j, k = 0, i
            while k < len(str) and str[j] == str[k]:
                j += 1
                k += 1
            Z[i] = j
            if j > 0:
                left, right = i, i+j-1
        else:
            z = Z[i-left]
            s = right-i+1
            if z < s:
                Z[i] = z
            else:
                j, k = s, s+i
                while k < len(str) and str[j] == str[k]:
                    j += 1
                    k += 1
                Z[i] = j
                left, right = i, i+j-1
        i += 1
    return Z

def similarity(s):
    return sum(zarray(s))

アルゴリズムの説明：

アイデアは単純です（ただし、ほとんどの優れたアイデアと同様に、簡単に作成することはできません）。文字列のプレフィックスでもある（空でない）サブストリングをprefix-substringと呼びましょう。再計算を回避するために、アルゴリズムは、現在考慮されているインデックスの前から始まり、最も右に伸びるプレフィックスサブストリングのウィンドウを使用します（最初は、ウィンドウは空です）。

使用される変数とアルゴリズムの不変量：

  • i、検討中のインデックスは、1から始まり（0ベースのインデックスの場合、文字列全体は考慮されません）、次のように増分されます。length - 1
  • leftおよびright、prefix-substringウィンドウの最初と最後のインデックス。不変量：
    1. left < i、、またはleft <= right < length(S)、、_left > 0right < 1
    2. の場合left > 0、S[left .. right]はとの最大の共通プレフィックスでSありS[left .. ]、
    3. 1 <= j < iおよびS[j .. k]がの接頭辞である場合S、k <= right
  • 配列Z、invariant：for 1 <= k < i、Z[k]には、との最長の共通プレフィックスの長さが含まれS[k .. ]ますS。

アルゴリズム：

  1. を設定i = 1しleft = right = 0（任意の値を使用できます）、すべてのインデックスleft <= right < 1に設定します。Z[j] = 01 <= j < length(S)
  2. の場合i == length(S)、停止します。
  3. の場合、との最長の共通プレフィックスのi > right長さを見つけて、に格納します。前よりも右に伸びるウィンドウが見つかった場合は、設定して、それ以外の場合は変更しないでください。インクリメントして2に進みます。lSS[i .. ]Z[i]l > 0left = iright = i+l-1i

  4. ここleft < i <= rightで、部分文字列S[i .. right]は既知です-はのS[left .. right]プレフィックスであるSため、はに等しくなりS[i-left .. right-left]ます。

    Sここで、インデックスで始まる部分文字列を持つの最長の共通プレフィックスについて考えてみますi - left。その長さはZ[i-left]、したがってS[k] = S[i-left + k]、0 <= k < Z[i-left]および
    S[Z[i-left]] ≠ S[i-left+Z[i-left]]です。さて、もし、ならZ[i-left] <= right-i、それi + Z[i-left]は既知のウィンドウの中にあるので、

    S[i + Z[i-left]] = S[i-left + Z[i-left]] ≠ S[Z[i-left]]
S[i + k]         = S[i-left + k]         = S[k]   for 0 <= k < Z[i-left]

    そして、との最長の共通接頭辞の長さが長さであることがSわかりS[i .. ]ますZ[i-left]。次に、を設定Z[i] = Z[i-left]し、インクリメントiして、2に進みます。

    それ以外の場合、S[i .. right]はの接頭辞でSあり、それがどこまで拡張されているかを確認し、インデックスright+1との文字の比較を開始しますright+1 - i。長さを。としますl。、、、インクリメントを設定Z[i] = lし、2に進みます。left = iright = i + l - 1i

ウィンドウが左に移動することはなく、比較は常にウィンドウの終了後に開始されるため、文字列内の各文字は、文字列内の前の文字と最大1回正常に比較され、開始インデックスごとに最大1つの失敗があります。したがって、アルゴリズムは線形です。

于 2012-09-24T21:29:57.063 に答える