python实现字符串匹配的Boyer-Moore算法

darkpoon

'''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[l1] != str2[l1]:
return (l1,str1[l1])
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[start:end]
cr = compare(string[start:end],des)
if cr[0] == -2:
print 'not found'
break
if cr[0] == 0:
return end - l
else:
pos = isCharactorIn(des,cr[1])
if cr[0] == (len(des)-1):
if pos != -1:
start += len(des) -1 - pos
else:
start += len(des)
else:
if pos == -1:
#                    have good  string
goodPos = isCharactorIn(des,des[l])
if goodPos == l:
start += l + 1
else:
start += l - goodPos
boyer_moore_search("here is a simple example", 'example')

　　以上是[size=1em]boyer-moore算法的实现，具体请看阮一峰blog