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

您的算法在最坏的情况下是二次的。对于大多数正常的单词，没有二次行为，并且它运行得很好（由于它的简单性，它可​​能比更复杂的算法运行得更快，并且具有更好的最坏情况行为）。

一种具有线性最坏情况行为的算法是 Z 算法。ruby我不会说太多，所以暂且，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))

算法说明：

这个想法很简单（但是，像大多数好想法一样，不容易拥有）。让我们将一个（非空）子字符串称为前缀子字符串，它也是字符串的前缀。为了避免重新计算，该算法使用前缀子字符串的窗口，该窗口在当前考虑的索引之前开始，向右延伸最远（最初，该窗口是空的）。

使用的变量和算法的不变量：

  • i，所考虑的索引，从 1 开始（对于基于 0 的索引；不考虑整个字符串）并递增到length - 1
  • left和right，前缀子字符串窗口的第一个和最后一个索引；不变量：
    1. left < i, left <= right < length(S),left > 0或者right < 1,
    2. 如果left > 0, 那么S[left .. right]是 and 的最大公共S前缀S[left .. ],
    3. 如果1 <= j < i和S[j .. k]是 的前缀S，则k <= right
  • 一个数组Z，不变量： for 1 <= k < i，包含andZ[k]的最长公共前缀的长度。S[k .. ]S

算法：

  1. 设置i = 1, left = right = 0（left <= right < 1允许任何值），并Z[j] = 0为所有索引设置1 <= j < length(S)。
  2. 如果i == length(S)，停止。
  3. 如果i > right，求和l的最长公共前缀的长度S，S[i .. ]将其存储在 中Z[i]。如果l > 0我们发现一个窗口比前一个窗口延伸得更远，则设置left = iand right = i+l-1，否则保持不变。递增i并转到 2。

  4. 在这里left < i <= right，子串S[i .. right]是已知的——因为它S[left .. right]是 的前缀S，所以它等于S[i-left .. right-left]。

    S现在考虑从 index 开始的子字符串的最长公共前缀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 .. ]有 length Z[i-left]。然后设置Z[i] = Z[i-left]，递增i，然后转到 2。

    否则，S[i .. right]是 的前缀，S我们检查它的扩展范围，开始比较索引处的字符right+1和right+1 - i。设长度为l。设置Z[i] = l, left = i, right = i + l - 1, increment i，然后转到 2。

由于窗口从不向左移动，并且比较总是在窗口结束后开始，因此字符串中的每个字符最多与字符串中较早的字符比较一次成功，并且对于每个起始索引，最多有一个不成功的比较，因此该算法是线性的。

于 2012-09-24T21:29:57.063 回答