boyer-moore.py

from collections import defaultdict

def generer_tableau(mot):
    d =  defaultdict(lambda : -1)
    for i in range(len(mot)):
        for j in range(i+1, len(mot)):
            d[(mot[i], j)] = i
    return d

def boyer_moore(t, m):
    dico = generer_tableau(m)
    i = 0
    while i <= len(t) - len(m):
        for j in range(len(m)-1, -1, -1):
            if t[i+j] != m[j]:
                break
        else:
            print("Occurence trouvée en position", i)
        i += j - dico[(t[i+j], j)]
        
boyer_moore("désencastrement", "en")