## Exercice 1

def occurences(L):
    dico = {}
    for x in L:
        if x in dico:
            dico[x] = dico[x] + 1
        else:
            dico[x] = 1
    return dico


## Exercice 2
# 1.

def compare_naif(L, M):
    N = M.copy()
    for x in L:
        j = 0
        trouve = False
        while j < len(N) and not trouve:
            if N[j] == x:
                trouve = True
                N.pop(j)
            else:
                j = j + 1
        if not trouve:
            return False
    return len(N) == 0


L1 = list(range(6)) + [2, 5]
L2 = [1, 3, 0, 2, 5, 5, 2, 4]
L3 = list(range(6))
print(compare_naif(L1, L2), compare_naif(L1, L3))


# Dans le pire des cas, lorsque les deux liste ont même longueur et les
# mêmes éléments, si la boucle while fait j tours, la fonction pop
# décale len(N) - j éléments; donc le cout de la boucle while est
# en O(len(N)) (les autres opérations sont en temps constant).
# Le nombre d'opérations est alors somme pour k de 0 à n 10*(n - k) = O(n^2)


## 2.

def inter(G, D):
    res = []
    i, j = 0, 0
    while i < len(G) and j < len(D):
        if G[i] < D[j]:
            res.append(G[i])
            i = i + 1
        else:
            res.append(D[j])
            j = j + 1
    if i == len(G):
        res.extend(D[j:])
    else:
        res.extend(G[i:])
    return res


def tri(L):
    n = len(L)
    if n < 2:
        return L
    else:
        G = tri(L[:n//2])
        D = tri(L[n//2:])
        return inter(G, D)


# print(tri(L2))

# la fonction tri est la fonction de tri fusion, sa complexité est
# quasi-linéaire en la longueur de la liste.


def compare_tri(L, M):
    n = len(L)
    if len(M) != n:
        return False
    L_trie = tri(L)
    M_trie = tri(M)
    for k in range(n):
        if L_trie[k] != M_trie[k]:
            return False
    return True


print(compare_tri(L1, L2), compare_tri(L1, L3))


# avant la boucle on a 6 opérations élémentaires et 2 appels à la fonction
# tri : soit 2n lg(n) opérations
# il y a n tours de boucle dans le pire des cas et 3 opérations à chaque tour,
# la complexité de la boucle et donc : 3n
# Donc : la complexité de la fonction compare_tri est n lg(n) : quasi-linéaire

## 3.

def compare_occ(L, M):
    dico_L = occurences(L)
    dico_M = occurences(M)
    if len(L) != len(M):
        return False
    for cle in dico_L:
        if cle not in dico_M:
            return False
        elif dico_M[cle] != dico_L[cle]:
            return False
    return True


print(compare_occ(L1, L2), compare_occ(L1, L3))

# avec n le maximum des longueurs de L et M, les appels à la fonctions
# occurences sont de complexité : O(n)
# le nombre de tours de boucle est au plus la longueur de dico_L
# qui est inférieur à n et le nombre d'opérations par tour est au plus 5;
# la complexité de la boucle for est donc : 5n
# donc : la complexité de la fonction compare_occ est linéaire : O(n)


## Exercice 3 : compression LZ78

def compresser_etape(texte, dico, code, i):
    k = i
    while k < len(texte) and texte[i:k] in dico:
        k += 1
    dico[texte[i:k]] = len(code) + 1
    code.append((dico[texte[i:k - 1]], texte[k - 1]))
    return k


def compresser_LZ78(texte):
    i = 0
    dico = {'': 0}
    code = []
    while i < len(texte):
        i = compresser_etape(texte, dico, code, i)
    return code


def code_to_mots(code):
    res = ['']
    for p, car in code:
        res.append(res[p] + car)
    return res


def decompresser_LZ78(code):
    L = code_to_mots(code)
    res = ''
    for mot in L:
        res = res + mot
    return res


ex1 = 'veridique ! dominique pique nique en tunique.'
ex2 = "babaababa"
code = compresser_LZ78(ex1)
decomp = decompresser_LZ78(code)
print(decomp)