# Un Trie stocke des chaînes de caractères en partageant les préfixes communs -- très efficace
# pour l'autocomplétion, la vérification orthographique, le routage IP (préfixes CIDR).

class NoeudTrie:
    def __init__(self):
        self.enfants: dict[str, "NoeudTrie"] = {}
        self.fin_de_mot: bool = False

class Trie:
    def __init__(self):
        self.racine = NoeudTrie()

    def inserer(self, mot: str) -> None:
        # O(longueur du mot) -- indépendant du nombre de mots déjà stockés
        noeud = self.racine
        for caractere in mot:
            if caractere not in noeud.enfants:
                noeud.enfants[caractere] = NoeudTrie()
            noeud = noeud.enfants[caractere]
        noeud.fin_de_mot = True

    def rechercher(self, mot: str) -> bool:
        # O(longueur du mot) -- le mot exact doit exister ET se terminer ici
        noeud = self._parcourir_prefixe(mot)
        return noeud is not None and noeud.fin_de_mot

    def commence_par(self, prefixe: str) -> bool:
        # O(longueur du préfixe) -- utile pour l'autocomplétion
        return self._parcourir_prefixe(prefixe) is not None

    def _parcourir_prefixe(self, prefixe: str) -> NoeudTrie | None:
        noeud = self.racine
        for caractere in prefixe:
            if caractere not in noeud.enfants:
                return None
            noeud = noeud.enfants[caractere]
        return noeud

    def mots_avec_prefixe(self, prefixe: str) -> list[str]:
        # Retourne tous les mots stockés qui commencent par ce préfixe
        noeud = self._parcourir_prefixe(prefixe)
        if noeud is None:
            return []
        resultats = []
        self._collecter_mots(noeud, prefixe, resultats)
        return resultats

    def _collecter_mots(self, noeud: NoeudTrie, prefixe_courant: str, resultats: list) -> None:
        if noeud.fin_de_mot:
            resultats.append(prefixe_courant)
        for caractere, enfant in noeud.enfants.items():
            self._collecter_mots(enfant, prefixe_courant + caractere, resultats)

    def supprimer(self, mot: str) -> bool:
        def _supprimer_recursif(noeud: NoeudTrie, mot: str, profondeur: int) -> bool:
            if profondeur == len(mot):
                if not noeud.fin_de_mot:
                    return False
                noeud.fin_de_mot = False
                return len(noeud.enfants) == 0   # True si le noeud peut être élagué
            caractere = mot[profondeur]
            if caractere not in noeud.enfants:
                return False
            doit_elaguer = _supprimer_recursif(noeud.enfants[caractere], mot, profondeur + 1)
            if doit_elaguer:
                del noeud.enfants[caractere]
                return len(noeud.enfants) == 0 and not noeud.fin_de_mot
            return False
        return _supprimer_recursif(self.racine, mot, 0)

trie = Trie()
for mot in ["chat", "chien", "chameau", "chaise"]:
    trie.inserer(mot)

assert trie.rechercher("chat") is True
assert trie.rechercher("cha") is False        # préfixe mais pas un mot complet
assert trie.commence_par("cha") is True
assert sorted(trie.mots_avec_prefixe("cha")) == ["chaise", "chameau", "chat"]

# --- Application : autocomplétion avec limite de suggestions ---
def suggerer(trie: Trie, prefixe: str, limite: int = 5) -> list[str]:
    return trie.mots_avec_prefixe(prefixe)[:limite]

# --- Application : compter les mots ayant un préfixe donné (variante avec compteur par noeud) ---
class NoeudTrieAvecCompteur:
    def __init__(self):
        self.enfants: dict[str, "NoeudTrieAvecCompteur"] = {}
        self.compteur_prefixe = 0   # nombre de mots passant par ce noeud
        self.fin_de_mot = False

class TrieAvecCompteur:
    def __init__(self):
        self.racine = NoeudTrieAvecCompteur()

    def inserer(self, mot: str) -> None:
        noeud = self.racine
        for c in mot:
            if c not in noeud.enfants:
                noeud.enfants[c] = NoeudTrieAvecCompteur()
            noeud = noeud.enfants[c]
            noeud.compteur_prefixe += 1
        noeud.fin_de_mot = True

    def compter_avec_prefixe(self, prefixe: str) -> int:
        # O(longueur du préfixe) -- pas besoin de parcourir tous les mots stockés
        noeud = self.racine
        for c in prefixe:
            if c not in noeud.enfants:
                return 0
            noeud = noeud.enfants[c]
        return noeud.compteur_prefixe