# Correction Boyer-Moore

# -----------------------------
# Exercice 1 : Recherche naïve
# -----------------------------

"""
Question 1:

0123456
BARBARA
AR
 AR
  AR
   AR
    AR
     AR

Question 2:

Sur les positions 1 et 4

Question 3:

n = taille de la chaine
m = taille du motif
En comptant à partir de 0, la dernière recherche est effectué sur le caractère n - m
En comptant à partir de 1, la dernière recherche est effectué sur le caractère n - m + 1

Question 4:

On a un pire cas si les trois caractère du motifs sont comparés. Il faut donc que le motif commence par AA (ex : AAA ou AAB)
On a un meilleur cas si la comparaison sur le premier caractère du motifs échoue. Il faut donc que le motif ne commence pas par A (ex : BAA ou CAA)

Question 5:

On effectue n - m +1 comparaisons dans le pire des cas, donc O(m-n)
"""

# Question 6

def correspond(M, T, i):
    j = 0
    while j < len(M):
        if M[j] != T[i + j]:
            return False
        j += 1
    return True

def recherche_naive(M, T):
    solution = []
    i = 0
    while i < len(T) - len(M) + 1:
        if correspond(M, T, i):
            solution.append(i)
        i += 1
    return solution
    
assert correspond('GCAG', 'GGCAGCCGAACCGCAGCAGCAC', 1) == True
assert correspond('GCAG', 'GGCAGCCGAACCGCAGCAGCAC', 0) == False
assert correspond('BRA', 'ABRACADABRA', 8) == True
assert recherche_naive('GCAG', 'GGCAGCCGAACCGCAGCAGCAC') == [1, 12, 15]
assert recherche_naive('TOTO', 'GGCAGCCGAACCGCAGCAGCAC') == []
assert recherche_naive('ar', 'barbara') == [1, 4]

# -----------------------------
# Exercice 2 : Algorithme de Boyer-Moore-Horspool
# -----------------------------

M = 'abracadabra'
T = 'bradacadabdabracadabratabracadabra'
"""
Question 1:

bradacadabdabracadabratabracadabra
abracadabra                             a != d, on aligne avec le dernier d
    abracadabra                         a != b, le dernier b est passé, on décale de 1
     abracadabra                        a != c, on aligne avec le dernier c
           abracadabra                  Motif trouvé, on décale de 1
            abracadabra                 a != t et t n'appartient pas au motif, on décale de la taille du motif + 1
                       abracadabra      Motif trouvé, fin
                       

Question 2:

Trouvé en 11 et 24

Question 3:
    
    Le pire des cas est avec AAA ou tout ce qui se termine par AA, on effectue 8 * 3 comparaisons.
    Le meilleur cas est tout ce qui ne contient pas de A, on effectue 3 comparaisons.
    AAAAAAAAAA
    ZZZ
       ZZZ
          ZZZ
          
Question 4:

r = 1
b = 2
a = 3
d = 4
c = 6
"""

# Question 5

def table_MC(M):
    d = {}
    for i in range(len(M) -1):
        d[M[i]] = len(M) -1 - i
    return d

print(table_MC('GCAG'))

# Question 6

print(table_MC('abracadabra'))

# Question 7

def BMH(M, T):
    # Prétraitement (Règle du mauvais caractère)
    MC  = table_MC(M)
    
    # Recherche par fenêtre glissante
    n = len(T)
    m = len(M)
    positions = []
    i = 0
    while i <= n - m : # i : position du motif
        j = m - 1 # comparaison à partir de la droite
        while j >= 0 and M[j] == T[i + j]:
            j = j - 1
        if j == - 1: #si motif trouvé
            positions.append(i)
            i = i + 1 # decalage de 1
        else: # si motif non trouvé ->> caractère fautif : T[i+j]
            if T[i+j] in MC: # si le caractère fautif T[i+j] est dans le maoif
                i = i + (1 if MC[T[i+j]] < j else MC[T[i+j]]) # on fait le décalage ne fonction de MC (DIFFICILE)
            else: # si le caractère fautif T[i+j] n'est pas dans le motif
                i = i + m # on place le motif après la position fautive
    return positions
    
assert BMH('abracadabra', 'bradacadabdabracadabratabracadabra') == [11, 23]
            
# Efficacité en pratique

fichier = open('ltdme80j.txt', mode = 'r', encoding='utf-8')
texte = fichier.read() # mémorisation dans une unique chaîne de caractères
fichier.close()
print(len(texte))
print(texte)

print(recherche_naive('Phileas', texte))
print(BMH('Phileas', texte))

assert recherche_naive('Phileas', texte) == BMH('Phileas', texte)