# TP 09 correction : Texte et mots
# BCPST1B 2026-2027
# Lycée Hoche, Versailles
# L.-C. LEFÈVRE

#%% exécuter pour la partie I

with open("livre.txt", "r", encoding="utf-8") as f:
    livre = f.read()[615:-18798]

# extrait du livre : le début et la fin
print(livre[:664])
print("\n[...]\n")
print(livre[-3:])
print("nombre de caractères :", len(livre))

#%% exercice 1.1

def cherche1(s, x):
    n = len(s)
    for i in range(n):
        if s[i] == x:
            print(i)

# test
s = "abracadabra"
x = "a"
print("x =", x)
cherche1(s, x)
x = "c"
print("x =", x)
cherche1(s, x)
x = "z"
print("x =", x)
cherche1(s, x)

#%% exercice 1.2

def compte1(s, x):
    n = len(s)
    c = 0
    for i in range(n):
        if s[i] == x:
            c = c +1
    return c

# test
s = "TTAGTATAATGAC"
print(compte1(s, "A"))
print(compte1(s, "G"))


#%% test dans le livre

print(compte1(livre, "e"))
print(compte1(livre, "x"))

#%% exercice 2.1

def cherche3(s, x, y, z):
    n = len(s)
    for i in range(n-2):
        if s[i] == x and s[i+1] == y and s[i+2] == z:
            print(i)

# test
s = "TTAGTATAATGAC"
cherche3(s, "A", "T", "G")

#%% exercice 2.2

def compte3(s, x, y, z):
    n = len(s)
    c = 0
    for i in range(n-2):
        if s[i] == x and s[i+1] == y and s[i+2] == z:
            c = c + 1
    return c

# test : à vous, dans le livre !
print(compte3(livre, "u", "n", "e"))

#%% exercice 3

def le_mot_est_ici(s, m, i):
    n = len(s)
    p = len(m)
    assert i + p <= n, "ce n'est pas possible, réfléchi"
    for j in range(p):
        if s[i+j] != m[j]:
            return False
    return True

# test
s = "TTAGTATAATGAC"
m = "ATG"
for i in range(len(s)-2):
    print(i, le_mot_est_ici(s, m, i))

#%% exercice 4.1

def cherche_mot(s, m):
    n = len(s)
    p = len(m)
    for i in range(n-p+1):
        if le_mot_est_ici(s, m, i):
            print(i)

# test
s = "abracadabra"
m = "abra"
print("m =", m)
cherche_mot(s, m)
m = "cad"
print("m =", m)
cherche_mot(s, m)

#%% exercice 4.2

def compte_mot(s, m):
    n = len(s)
    c = 0
    for i in range(n):
        if le_mot_est_ici(s, m, i):
            c = c + 1
    return c

# test dans le livre
m = "amour"
print("m =", m)
print(compte_mot(livre, m))

#%% bonus

# afficher les mots avec un certain nombre de caractères avant et après
def cherche_mot_plus(s, m):
    n = len(s)
    p = len(m)
    for i in range(n):
        if le_mot_est_ici(s, m, i):
            if i - 30 >= 0 and i + p + 30 < n:
                print(s[i-30:i+p+30].replace("\n", " "))

# test
cherche_mot_plus(livre, "amour")

#%% exécuter pour la partie II

with open("dictionnaire.txt", "r", encoding="utf-8") as f:
    dictionnaire = [s.strip() for s in f]

print("longueur du dictionnaire:", len(dictionnaire))
# extrait : un mot tous les 50000
print("un extrait :")
print(dictionnaire[::50000])

#%% exercice 5

def est_présent(m):
    for i in range(len(dictionnaire)):
        if dictionnaire[i] == m:
            return True
    return False

# test
m = "python"
print(m, est_présent(m))
m = "ortaugraffe"
print(m, est_présent(m))

#%% exercice 6

def distance(s, t):
    assert len(s) == len(t), "les deux mots doivent être de même longueur"
    n = len(s)
    d = 0
    for i in range(len(s)):
        if s[i] != t[i]:
            d = d + 1
    return d

# test
print(distance("vacances", "savantes"))

#%% exercice 7

def cherche_seuil(m, seuil):
    p = len(m)
    for i in range(len(dictionnaire)):
        if len(dictionnaire[i]) == p:
            if distance(dictionnaire[i], m) <= seuil:
                print(dictionnaire[i])

# test
m = "vacances"
cherche_seuil(m, 2)

#%% exercice 7

def mots_les_plus_proches(m):
    p = len(m)
    # étape 1 : calcul de la distance minimale
    dmin = p
    for i in range(len(dictionnaire)):
        if len(dictionnaire[i]) == p:
            d = distance(dictionnaire[i], m)
            if d < dmin:
                dmin = d
    # étape 2 : afficher tous les mots à distance dmin
    print("distance minimale :", dmin)
    for i in range(len(dictionnaire)):
        if len(dictionnaire[i]) == p:
            if distance(dictionnaire[i], m) == dmin:
                print(dictionnaire[i])

# test
# Si le mot existe déjà, la distance minimale est 0 et la fonction ne trouvera que m lui-même…
m = "ortaugraffe"
print("m =", m)
mots_les_plus_proches(m)
m = "rekurranse"
print("m =", m)
mots_les_plus_proches(m)

#%% exercice 9

def liste_mots_les_plus_proches(m):
    p = len(m)
    # initialisation : liste vide, la distance est au plus p
    L = []
    dmin = p
    for i in range(len(dictionnaire)):
        if len(dictionnaire[i]) == p:
            d = distance(dictionnaire[i], m)
            # on trouve un élément à distance dmin : l'ajouter à la liste
            if d == dmin:
                L.append(dictionnaire[i])
            # on trouve un élément à distance plus petite : c'est le nouveau minimum et on oublie le reste de la liste
            elif d < dmin:
                L = [dictionnaire[i]]
                dmin = d
            # sinon : un élément à distance plus grande, on ne fait rien
    return L

# test
m = "ortaugraffe"
print("m = ", m)
print(liste_mots_les_plus_proches(m))
m = "rekurranse"
print("m = ", m)
print(liste_mots_les_plus_proches(m))

#%% exercice 10.1

def est_acceptable(s, m):
    assert len(s) == len(m), "les deux mots doivent être de même longueur"
    n = len(s)
    for i in range(n):
        # parmi les caractères non *
        if s[i] != "*":
            # les caractères doivent coïncider
            if s[i] != m[i]:
                return False
    return True

# test
print(est_acceptable("p*t*on", "python"))
print(est_acceptable("p*t*on", "poison"))

#%% exercice 10.2

def complète(s):
    n = len(s)
    for i in range(len(dictionnaire)):
        if len(dictionnaire[i]) == n:
            if est_acceptable(s, dictionnaire[i]):
                print(dictionnaire[i])

# test
complète("p*t*on")

#%% exercice 11.1

def est_bord(m, k):
    p = len(m)
    for j in range(k):
        if m[j] != m[p-k+j]:
            return False
    return True

# test
m = "AGTCGAGT"
print("m =", m)
for k in range(len(m)):
    print(k, est_bord(m, k))

#%% exercice 11.2

def longueur_bord(m):
    p = len(m)
    # calcul de maximum
    t = 0
    for k in range(p):
        if est_bord(m, k):
            t = k
    return t

# test
m = "AGTCGAGT"
print("m =", m)
print(longueur_bord(m))
m = "TTTGCCTTT"
print("m =", m)
print(longueur_bord(m))
m = "AGTCGAGTC"
print("m =", m)
print(longueur_bord(m))
m = "AGTCGACTC"
print("m =", m)
print(longueur_bord(m))

#%% exercice 11.3

def longueurs_bords_prefixes(m):
    p = len(m)
    # ici on triche un peu avec une tranche de m ;
    # sinon il faut modifier la fonction longueur_bord pour s'arrêter à l'indice j
    L = [longueur_bord(m[:j+1]) for j in range(p)]
    return L

m = "AATGAATC"
print("m =", m)
print(longueurs_bords_prefixes(m))

#%% exercice 12

def cherche_KMP(s, m):
    n = len(s)
    p = len(m)
    B = longueurs_bords_prefixes(m)
    i = 0
    j = 0
    while i <= n - p:
        while j < p and m[j] == s[i+j]:
            j = j + 1
        if j == p:
            print("Trouvé à", i)
            i = i + 1
            j = 0
        elif j == 0:
            print("Ne démarre pas à", i, "saut de", 1)
            i = i + 1
            j = 0
        else:
            print("Ne démarre pas à", i, "saut de", j - B[j-1])
            i = i + j - B[j-1]
            j = B[j-1]

# tests

s = "AGTAGCAGCT"
m = "AGCT"
print("s =", s)
print("m =", m)
cherche_KMP(s, m)

s = "ACACATAG"
m = "ACAT"
print("s =", s)
print("m =", m)
cherche_KMP(s, m)

s = "ATCGATCGATCGATG"
m = "ATCGATG"
print("s =", s)
print("m =", m)
cherche_KMP(s, m)
