Rencontre #2: Chaînes de caractères

Dans cette deuxième rencontre, nous avons commencé par discuter des solutions de la série de problèmes sur la géométrie.

Problèmes

Nous nous sommes ensuite penchés sur la série de problèmes suivante, sur la thématique des chaînes de caractères. Les problèmes sont en ordre croissant de difficulté.

1. “Avion” — Identifiez, parmi un ensemble de chaînes de caractères, celles qui contiennent une occurrence d’un motif prédéfini.
2. “Pebble Solitaire” — Dans cette variante du solitaire à une dimension, vous devez calculer une séquence de coups permettant d’éliminer le plus de pions possible.
3. “Bing It On” — On vous fournit une liste de mots. Pour chacun de ces mots, calculez le nombre de mots précédents dont il est un préfixe.
4. “String Factoring” — Trouvez la meilleure façon de compresser les répétitions dans une chaîne de caractères.
5. “Automatic Trading” — Calculez le plus long préfixe commun à des paires de suffixes d’une chaîne de caractères.

Ressources

Voici quelques ressources utiles pour lire et pratiquer sur le sujet des chaînes de caractères:

• la section “String Processing” du site web cp-algorithms.com recense des algorithmes de chaînes de caractères et des problèmes avec des implémentations en C++;
• le chapitre 2 du livre “Programmation efficace” de C. Dürr et J.-J. Vie traite d’algorithmes pour les chaînes de caractères et propose des implémentations en Python;
• les sections 14.1 et 14.2 du livre “Guide to Competitive Programming” de A. Laaksonen couvrent également les algorithmes essentiels pour ce sujet;
• la section “String Algorithms” du site CSES regroupe des problèmes classiques de chaînes de caractères auxquels vous pouvez vous essayer (il suffit de créer un compte pour pouvoir soumettre).