#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Mon May 11 14:27:24 2026

@author: pjoulaud
"""

motif = "papas"
texte = "un papou papa à poux a des poux papas et des poux pas papas"

motif = "ACCTTCG"
texte = "CAATGTCTGCACCAAGACGCCGGCAGGTGCAGACCTTCGTTATAGGCGATGATTTCGAACCTACTAGTGGGTCTCTTAGGCCGAGCGGTTCCGAGAGATAGTGAAAGATGGCTGGGCTGTGAAGGGAAGGAGTCGTGAAAGCGCGAACACGAGTGTGCGCAAGCGCAGCGCCTTAGTATGCTCCAGTGTAGAAGCTCCGGCGTCCCGTCTAACCGTACGCTGTCCCCGGTACATGGAGCTAATAGGCTTTACTGCCCAATATGACCCCGCGCCGCGACAAAACAATAACAGTTT"

# dico = {'s':5, 'a':1, 'p':2}

def creation_dico(M):
    d = {}
    m = len(M)
    for i in range(1,m) :
        if M[m-i-1] not in d :
            d[M[m-i-1]] = i
    return d


def recherche_boyer_moore(M, T):
    dico = creation_dico(M)
    print(dico)
    decalage = 0
    m, t = len(M), len(T)
    while decalage+m<=t:
        j = m-1
        print(M[j], " - texte : ", T[decalage+j])
        while j>0 and M[j]==T[decalage+j]:
            # print('j :', j)
            j -= 1
        if j==0 :
            print("trouvé à i : ", decalage)
            decalage = decalage + m
        else :
            lettre_differente = T[decalage+j]
            if lettre_differente in dico :
                decalage = decalage + dico[lettre_differente]
                # print(dico[lettre_differente])
            else :
                decalage = decalage + m
                # print(m)
        # input()
# print(creation_dico('papas')                )
recherche_boyer_moore(motif, texte)