Autocomplétion

Dans cet exercice, nous allons développer puis utiliser une stucture appelée « trie ».

Vous créerez donc une classe Trie qui fera office de dictionnaire.
Il sera possible d'y ajouter des mots puis de récupérer efficacement ceux commençant par un préfixe donné.

Cette structure initialement vide sera basée sur un arbre dont on détiendra la racine.
Comme tous les autres nœuds de l'arbre, la racine tiendra à jour une liste de fils correspondant aux suffixes acceptés, chaque suffixe étant lui-même un arbre.
La structure grandira à mesure que l'on ajoutera de nouveaux mots à travers une méthode nommée ajouter qui acceptera un mot en guise de paramètre.

Pour coder la class Trie, vous aurez besoin d'une classe Noeud qui possèdera trois attributs :

Pour construire votre dictionnaire, vous pourrez utiliser cette liste de mots.
Afin de gérer correctement l'encodage UTF-8 du fichier, faites appel à std::locale ou directement à std::codecvt.

Il sera alors possible d'effectuer des recherches à l'aide de la méthode chercher.
Cette méthode acceptera comme paramètre le préfixe correspondant au début du mot saisi par l'utilisateur et elle fournira comme résultat la liste des suggestions compatibles.