Boyer-Moore

def comparer(texte: str, motif: str, pos: int) -> bool:
    j = 0
    while (j < len(motif)) and (motif[j] == texte[pos + j]):
        j += 1
    # correspondance sur toute la fenêtre
    return j == len(motif)


def decaler(pos: int) -> int:
    return pos + 1


def recherche_naive(texte: str, motif: str) -> int:
    """
    renvoie la position du motif dans le texte
    -1 s'il n'est pas présent
    """
    # dernière position = taille(texte) - taille(motif)
    position = 0
    while position <= len(texte) - len(motif):
        if comparer(texte, motif, position):
            return position
        else:
            position = decaler(position)
    return -1


t = "atgatccatca"
assert recherche_naive(t, "cat") == 6
assert recherche_naive(t, "tca") == 8
assert recherche_naive(t, "dog") == -1

def pretraitement(motif: str) -> dict:
    """
    renvoie le dictionnaire des décalages à appliquer
    pour chaque lettre du motif (sauf dernière)
    """
    decalages = dict()
    # on s'arrête à l'avant dernière lettre du motif
    for i in range(len(motif) - 1):
        # len(motif)-1 est la position de la dernière lettre
        decalages[motif[i]] = len(motif) - 1 - i
    return decalages


def decaler(pos: int, decalages: dict, taille: int, lettre: str) -> int:
    if lettre in decalages:
        return pos + decalages[lettre]
    else:
        # si la lettre n'est pas dans le dico (= le motif)
        return pos + taille


def decaler2(decalages: dict, taille: int, lettre: str) -> int:
    try:
        res = decalages[lettre]
    except KeyError:
        res = taille
    return res


def comparer(texte: str, motif: str, pos: int) -> bool:
    j = 0
    while (j < len(motif)) and (motif[j] == texte[pos + j]):
        j += 1
    # correspondance sur toute la fenêtre
    return j == len(motif)


def horspool(texte: str, motif: str) -> int:
    """
    Returns:
        int: la position du motif dans le texte, -1 sinon.
    """
    decalages = pretraitement(motif)
    position = 0
    while position <= len(texte) - len(motif):
        if comparer(texte, motif, position):
            return position
        else:
            position = decaler(
                position, decalages, len(motif), texte[position + len(motif) - 1]
            )
    # si on sort de la boucle, on n'a rien trouvé
    return -1


assert pretraitement("cat") == {'c': 2, 'a': 1}
assert pretraitement("ring_ring") == {'r': 3, 'i': 2, 'n': 1, 'g': 5, '_': 4}

t = "atgatccatca"
assert horspool(t, "cat") == 6
assert horspool(t, "tca") == 8
assert horspool(t, "dog") == -1

t = "stupid_spring_ring"
m = "ring_ring"
assert horspool(t, m) == 9