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
  • leftright,前缀子字符串窗口的第一个和最后一个索引;不变量:
    1. left < i, left <= right < length(S),left > 0或者right < 1,
    2. 如果left > 0, 那么S[left .. right]是 and 的最大公共S前缀S[left .. ],
    3. 如果1 <= j < iS[j .. k]是 的前缀S,则k <= right
  • 一个数组Z,不变量: for 1 <= k < i,包含andZ[k]的最长公共前缀的长度。S[k .. ]S

算法:

  1. 设置i = 1, left = right = 0left <= right < 1允许任何值),并Z[j] = 0为所有索引设置1 <= j < length(S)
  2. 如果i == length(S),停止。
  3. 如果i > right,求和l的最长公共前缀的长度SS[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+1right+1 - i。设长度为l。设置Z[i] = l, left = i, right = i + l - 1, increment i,然后转到 2。

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

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