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[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')

 以上是boyer-moore算法的实现，具体请看阮一峰blog