您的算法在最坏的情况下是二次的。对于大多数正常的单词,没有二次行为,并且它运行得很好(由于它的简单性,它可能比更复杂的算法运行得更快,并且具有更好的最坏情况行为)。
一种具有线性最坏情况行为的算法是 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
,前缀子字符串窗口的第一个和最后一个索引;不变量:
left < i
, left <= right < length(S)
,left > 0
或者right < 1
,
- 如果
left > 0
, 那么S[left .. right]
是 and 的最大公共S
前缀S[left .. ]
,
- 如果
1 <= j < i
和S[j .. k]
是 的前缀S
,则k <= right
- 一个数组
Z
,不变量: for 1 <= k < i
,包含andZ[k]
的最长公共前缀的长度。S[k .. ]
S
算法:
- 设置
i = 1
, left = right = 0
(left <= right < 1
允许任何值),并Z[j] = 0
为所有索引设置1 <= j < length(S)
。
- 如果
i == length(S)
,停止。
- 如果
i > right
,求和l
的最长公共前缀的长度S
,S[i .. ]
将其存储在 中Z[i]
。如果l > 0
我们发现一个窗口比前一个窗口延伸得更远,则设置left = i
and right = i+l-1
,否则保持不变。递增i
并转到 2。
在这里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。
由于窗口从不向左移动,并且比较总是在窗口结束后开始,因此字符串中的每个字符最多与字符串中较早的字符比较一次成功,并且对于每个起始索引,最多有一个不成功的比较,因此该算法是线性的。