L'Atelier Monstre

Introduction à l'arbre de préfixes L'arbre de préfixes, communément appelé Trie, est une structure de données arborescente spécialisée dans la gestion et la recherche de chaînes de caractères. Contrairement à une table de hachage classique, le Trie exploite les préfixes communs entre les clés pour optimiser l'espace mémoire et la vitesse de rec ...

Problème A – Déplacement optimal sur une ligne On dispose d’un point situé en x et d’une cible en y. À chaque seconde on peut avancer d’au plus k unités. Le coût est simplement la position finale. Si x ≥ y, on atteint déjà la cible ; sinon on avance jusqu’à min(y, x+k) puis on rebrousse chemin pour atteindre y. Le temps total est donc y + (y - ...

Liste Simplement Chaînée Cette implémentation utilise des tableaux statiques pour simuler une liste chaînée, ce qui est particulièrement efficace en programmation compétitive pour éviter les allocations dynamiques coûteuses. // tete : indice du premier élément // val[] : stocke les données // suivant[] : pointeur vers l'indice suivant // curseu ...

L'automate d'Aho-Corasick est un algorithme puissant de recherche de motifs multiples, permettant de localiser toutes les occurrences d'un ensemble de mots-clés (motifs) à l'intérieur d'un texte donné. Il combine les concepts d'un arbre de préfixes (Trie) et de la fonction d'échec de l'algorithme de Knuth-Morris-Pratt (KMP) pour réaliser une re ...

Le problème consiste à identifier le sous-tableau, au sein d'un tableau d'entiers donné, dont la somme XOR (ou exclusif) est la plus élevée possible. Si le tableau d'entrée contient n nombres, l'objectif est de trouver max(a[i] ^ a[i+1] ^ ... ^ a[j]) pour tous les 0 <= i <= j < n. Format d'entrée La première ligne contient un entier n, ...