Tries pour les recherches par préfixe
Stocker et rechercher rapidement des préfixes de mots
Tries pour les recherches par préfixe est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Stocker intelligemment les mots
Un arbre de préfixes est un arbre qui stocke les mots en partageant leurs préfixes communs. Il rend les requêtes sur les préfixes extrêmement rapides. 🌳
Pourquoi ne pas utiliser simplement un ensemble
Un ensemble répond aux recherches de mots complets, mais les arbres de préfixes répondent aussi aux requêtes sur les préfixes, par exemple pour savoir si un mot commence par « pré ».
Nœuds et arêtes
Chaque nœud représente une position dans un mot, et chaque arête est étiquetée par un caractère du chemin partant de la racine.
Les enfants dans un dictionnaire
En Python, le nœud le plus simple est un dictionnaire associant chaque caractère à son nœud enfant. C’est simple et flexible.
root = {}Insérer un mot
Pour insérer un mot, parcourez-le caractère par caractère et créez un enfant chaque fois qu’il en manque un.
node = root
for c in word:
node = node.setdefault(c, {})Marquer la fin des mots
Après l’insertion, définissez un indicateur de fin afin de distinguer un mot complet d’un simple préfixe.
node['#'] = TrueRechercher un mot complet
Pour rechercher un mot, suivez ses caractères ; si une étape manque, le mot est absent. Vérifiez ensuite l’indicateur de fin.
for c in word:
if c not in node:
return False
node = node[c]Vérifier un préfixe
Une requête sur un préfixe suit le même chemin, mais sans vérifier l’indicateur de fin. Atteindre le dernier nœud suffit pour répondre oui.
Complexité temporelle
L’insertion et la recherche coûtent O(L), où L est la longueur du mot, quel que soit le nombre de mots stockés. Seule la longueur compte.
Compter les mots par préfixe
Stockez un compteur dans chaque nœud pour répondre instantanément au nombre de mots stockés qui partagent un préfixe donné.
À quoi servent les arbres de préfixes
Les arbres de préfixes permettent la complétion automatique, la vérification dans un dictionnaire et la résolution de problèmes de maximum de XOR sur des bits. C’est un outil incontournable des problèmes de chaînes en concours.
Vérification rapide
Vérifiez le coût réel d’une recherche dans un arbre de préfixes.
Récapitulatif : les arbres de préfixes, c’est fait
Vous savez maintenant construire un arbre de préfixes, insérer et rechercher en O(L), et répondre rapidement aux requêtes sur les préfixes et les nombres d’occurrences. 🌟
Questions Fréquemment Posées
La leçon « Tries pour les recherches par préfixe » est-elle gratuite ?
Oui — le texte complet de « Tries pour les recherches par préfixe » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Tries pour les recherches par préfixe » ?
Stocker et rechercher rapidement des préfixes de mots Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.
Combien de temps prend la leçon « Tries pour les recherches par préfixe » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Fonction préfixe KMP
- Hachage polynomial de chaînes
- Fonction Z pour rechercher un motif
- Tries pour les recherches par préfixe