python实现字符串匹配的Boyer-Moore算法
'''http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html'''def isCharactorIn(s,c):
try:
pos = s.index(c)
except ValueError:
pos = -1
return pos
def compare(str1,str2):
l1 = len(str1) - 1
l2 = len(str2) - 1
if l1 != l2:
return (-2,None)
while l1 >= 0:
if str1 != str2:
return (l1,str1)
l1 -= 1
return (0,None)
def boyer_moore_search(string, des):
l = len(des) - 1
strlen = len(string)-1
start,end = 0,0
while strlen >= 0:
end = start + len(des)
print string
cr = compare(string,des)
if cr == -2:
print 'not found'
break
if cr == 0:
return end - l
else:
pos = isCharactorIn(des,cr)
if cr == (len(des)-1):
if pos != -1:
start += len(des) -1 - pos
else:
start += len(des)
else:
if pos == -1:
# have goodstring
goodPos = isCharactorIn(des,des)
if goodPos == l:
start += l + 1
else:
start += l - goodPos
boyer_moore_search("here is a simple example", 'example')
以上是boyer-moore算法的实现，具体请看阮一峰blog
页:
[1]