from math import floor


SANS_ACCENT = {"À":"A", "Ä":"A", "Â":"A", "É":"E", "È":"E", "Ë":"E", "Ê":"E",
                "Î":"I", "Ï":"I", "Ô":"O", "Ö":"O", "Ù":"U", "Û":"U"}

def maj_sans_accent(chaine:str) -> str:
    """
    renvoie une copie de chaine en majuscule sans accent
    """
    chaine = chaine.upper()      # la chaine en MAJUSCULE
    copie = ""
    for car in chaine:
        if car in SANS_ACCENT:
            nouv_car = SANS_ACCENT[car]
        else :
            nouv_car = car
        copie = copie + nouv_car
    return copie


assert maj_sans_accent("à") == "A"
assert maj_sans_accent("Ô") == "O"
assert maj_sans_accent("hé hè hê") == "HE HE HE"

def distance(motA, motB):
    """
    renvoie une mesure de distance entre les deux mots
    """
    return 1 - jaro(maj_sans_accent(motA), maj_sans_accent(motB))

def jaro(s1, s2):
    """
    Implémente la distance de Jaro entre deux chaînes
    1.0 pour des chaînes identiques,
    0.0 pour des chaînes complètement différentes
    """
    if (s1 == s2):
        return 1.0
    len1 = len(s1)
    len2 = len(s2)
    max_dist = floor(max(len1, len2) / 2) - 1
    match = 0
    hash_s1 = [0] * len(s1)
    hash_s2 = [0] * len(s2)
    for i in range(len1):
        for j in range(max(0, i - max_dist), 
                    min(len2, i + max_dist + 1)):
            if (s1[i] == s2[j] and hash_s2[j] == 0):
                hash_s1[i] = 1
                hash_s2[j] = 1
                match += 1
                break
    if (match == 0):
        return 0.0
    t = 0
    point = 0
    for i in range(len1):
        if (hash_s1[i]):
            while (hash_s2[point] == 0):
                point += 1
            if (s1[i] != s2[point]):
                t += 1
            point += 1
    t = t//2
    return (match/ len1 + match / len2 +
            (match - t) / match)/ 3.0

# illustration :
# la région mal orthographiée "il de frce" est plus proche de "Île de France" que de "Bourgogne"
assert distance("Île de France", "il de frce") < distance("Bourgogne", "il de frce")