对于在字符串中查找子字符串的位置,一个简单的算法将花费O(n^2)
时间。然而,使用一些有效的算法(例如KMP algorithm),这可以在O(n)时间内实现:
s = 'saurabh'
w = 'au'
def get_table():
i = 0; j = 2
t = []
t.append(-1); t.append(0)
while i < len(w):
if w[i] == w[j-1]:
t.append(j+1)
j += 1
else:
t.append(0)
j = 0
i += 1
return t
def get_word():
t = get_table()
i = j = 0
while i+j < len(s):
if w[j] == s[i+j]:
if j == len(w) - 1:
return i
j += 1
else:
if t[j] > -1:
i = i + j - t[j]
j = t[j]
else:
i += 1
return -1
if __name__ == '__main__':
print get_word()
但是,如果我们这样做:'saurabh'.index('ra')
,它是在内部使用某种有效的算法来计算O(n)
,还是使用简单的复杂算法O(n^2)
?在
有时候你只要试一下就能得到一个快速的答案
它是一些算法的组合-看看这个
Python string 'in' operator implementation algorithm and time complexity
或者这个
http://effbot.org/zone/stringlib.htm
在那篇文章[1]中,作者详细介绍了算法并对其进行了解释。来自文章:
从Boyer-Moore-horsool算法的wiki页面来看:
^{pr2}$希望有帮助!在
[1]http://www.laurentluce.com/posts/python-string-objects-implementation
[2]https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm
相关问题 更多 >
编程相关推荐